Call a real $x$ limit computable iff there is a Turing machine $T$ such that, for any $i\in\omega$, there is $t(i)\in\omega$ such that the $i$th entry on the tape is not changed after time $t(i)$ and is from that time on equal to $1$ if $i\in x$ and otherwise equal to $0$. Intuitively, this means that the output of $T$ converges to $x$, though not at any effective rate.

Let us now consider transfinite iterations of this process: Define the Turing calcuation of a machine $T$ along an ordinal time axis by letting $T$ work classically at successor stages and at limit steps $\lambda$, let the tape content $B_{i\lambda}$ of cell $i$ be the eventually constant value of $(B_{i\alpha}|\alpha<\lambda)$ if that sequence is eventually constant. If it isn't for some $i\in\omega$, the calculation is undefined. The machine state and the head position at time $\lambda$ are taken to be the limes inferiors of the earlier states/head positions.

These calculations are similar to infinite time Turing machine calculations with arbitrary time and tape length $\omega$, but probably much weaker, as the 'eventually constant' rule for the tape content is much more restrictive than the liminf-rule of $ITTM$s.

My question is: Has this computability concept been studied? If yes, I would be thankful for references. If no, are there obvious reasons why not? (E.g. it is trivial, or obviously equivalent to well-studied notion XY...)


Yes, this notion has been studied. It is considerably weaker than the model of infinite time Turing machines. To see this, observe that your machines can never do anything after time $\omega^2$, because whatever local configuration the machine is in at time $\omega^2$ must have arisen many times earlier, and so whatever bit it would change then it must have changed earlier, which would have caused it to crash at $\omega^2$.

Meanwhile, if you are careful in arranging your computation, you can compute all arithmetic assertions in time uniformly less than $\omega^2$.

  • $\begingroup$ Thanks. Can you point me to a reference where this concept is considered? In particular, which reals can these machines compute? $\endgroup$ – M Carl Nov 9 '12 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.