0
$\begingroup$

On the one hand, I have read that Infinite Time Turing Machines (ITTMs) are able to determine whether a given input corresponds to a real that encodes a well-order (assuming that there exists a fixed, ITTM-computable way to encode a well-order of natural numbers into a single real number).

On the other hand, I have read that there exists a notion of reals recognizable by ITTMs, that is, basically, there exist real numbers that satisfy a given set of properties, but ITTMs are not able to determine whether a given real satisfies these properties.

The question is: are ITTMs able to recognize well-orders for arbitrarily large countable ordinals? If not, what is the smallest (countable) ordinal $\alpha$ such that if a real encodes a well-order of order type $\beta \ge \alpha$, there does not exist an ITTM which is able to recognize this fact?

$\endgroup$
  • $\begingroup$ There is one point that I might add. The answer assumes three $\omega$ tapes. It seems that two should also be enough though (I haven't thought of details but it seems interesting to work-out the details a bit). If you assume one $\omega$ tape then there is a possible subtlety. Think about how a single tape would simulate a three tape machine (by organizing the cells in groups of three). But if the input is a real number it isn't immediately obvious how to convert the given real to the required format for simulation. $\endgroup$ – SSequence Oct 28 '19 at 11:45
  • $\begingroup$ Here is a related topic: mathoverflow.net/questions/216065. I haven't read it, I am just linking it because it is relevant to above comment. Though as far as functions from $\mathbb{N}$ to $\mathbb{N}$ are concerned, number $n \in \mathbb{N}$ of $\omega$ tapes don't matter. $\endgroup$ – SSequence Oct 28 '19 at 11:46
1
$\begingroup$

The question is: are ITTMs able to recognize the presence of an arbitrarily large countable ordinal in a given well-order?

Strictly speaking, this is a little vague. A given real number (encoding a well-order) by definition corresponds to a unique ordinal $\alpha$. I think what you mean to say is: "are ITTMs able to recognize well-orders for arbitrarily large countable ordinals?"


Regarding your question, there are two different notions. The first part below is a bit longer (but I have tried to repeat the same point a few times).

(1) There exists a single ITTM that will always halt with a $\{0,1\}$ when given an arbitrary real number (say on the input tape), essentially as an input. The $0$ would mean that the real number doesn't represent a well-order (on $\mathbb{N}$) with order-type $\alpha$ (for some countable $\alpha$). $1$ would mean that the real number does represent a well-order (on $\mathbb{N}$) with order-type $\alpha$ (for some countable $\alpha$).

So for the question:

If not, what is the smallest (countable) ordinal $\alpha$ such that if a real encodes a well-order of order type $\alpha$, there does not exist an ITTM which is able to recognize this fact?

Based on what I said in last paragraph, I will reiterate this point again. There exists a single ITTM which will decide the real number as encoding a well-order or not (for arbitrarily large $\alpha$).

If the real number was present on input tape at the beginning of computation, then it doesn't matter how large or small $\alpha$ is. As long as $\alpha$ is countable and the corresponding real number encodes $\alpha$ (in the sense of well-order), then the given ITTM will run for roughly time $\alpha$ and then halt and give a $1$. If the real number doesn't encode a well-order then the ITTM would still halt and give a $0$ as output at some point.

So in that sense, a single ITTM not only "recognizes" (in the sense that it halts for a positive answer) but actually "decides" (in the sense that it halts for both positive and negative answers) for any given real-number whether it encodes a well-order or not.

(2) On the other hand, consider an ITTM starts from blank input. Then there are few different notions.

One is that it halts after sometime with a real as output on its tape. In that case, the real number on output (if it encodes a well-order at all) will encode a well-order with order-type $<\gamma$ (the $\gamma$ being sup of writeable ordinals).

The second notion is that it never halts but the output becomes stable after a certain time (and never changes after that). In that case the real number on output (if it encodes a well-order at all) will encode a well-order with order-type $<\zeta$ (the $\zeta$ being sup of eventually writeable ordinals).

$\endgroup$

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.