Continuing the study of complexity theory of Koepke's Ordinal Turing Machines (OTMs) that was started by Rin, L\"owe and the author, we prove the following results: (1) An analogue of Ladner's theorem for OTMs holds: That is, there are languages $\mathcal{ L}$ which are NP$^{ \infty}$, but neither P$^{ \infty}$ nor NP$^{ \infty}$-complete. This answers an open question of \cite{ CLR}. (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 $\alpha<\beta$ such that $\alpha$ is the halting time of some OTM-program, there are decision problems that are OTM-decidable in time bounded by $|w|^{ \beta}\cdot\gamma$ for some $\gamma\in\text{ On}$, but not in time bounded by $|w|^{ \alpha}\cdot\gamma$ for any $\gamma\in\text{ On}$.
Categories: math.LO