2018/01/30 by Carl, Merlin
#FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1801.10027
Continuing the study of complexity theory of Koepke's Ordinal Turing Machines (OTMs) that was started by Rin, Löwe and the author, we prove the following results: (1) An analogue of Ladner's theorem for OTMs holds: That is, there are languages L which are NP∞, but neither P∞ nor NP∞-complete. This answers an open question of \citeCLR. (2) The speedup theorem for Turing machines, which allows us to bring down the computation time and space usage of a Turing machine program down by an aribtrary positive factor under relatively mild side conditions by expanding the working alphabet does not hold for OTMs. (3) We show that, for α