# Does there exist a countable ordinal $\alpha$ such that a well-order of order type $\alpha$ is not recognizable by an Infinite Time Turing Machine?

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?

• 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. – SSequence Oct 28 '19 at 11:45
• 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. – SSequence Oct 28 '19 at 11:46

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).