This master thesis investigates space complexity theory, with the motivation of developing a degree theory. A direct application of our investigation is a strengthening of the space hierarchy theorem as stated by Sipser [Sipser, 2006]. At the end, we define a degree theory and show some elementary properties of the degree structure. We also present detailed proofs of known results, including a detailed description of a universal Turing machine.
| IFI link | thesis at DUO |