6
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Some Observations on Infinitary Complexity

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

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}$$.

### Most cited references6

• Record: found
• Abstract: found

### Infinite time Turing machines

(2000)
We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every set. for example, is decidable by such machines, and the semi-decidable sets form a portion of the sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.
Bookmark
• Record: found

### An Enhanced Theory of Infinite Time Register Machines

(2008)
Bookmark
• Record: found

### Infinite Time Register Machines

(2006)
Bookmark

### Author and article information

###### Journal
30 January 2018
###### Article
1801.10027