Xrfgtjtk

I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $alpha$ if $alpha$ is a computable ordinal: basically, we take the description of some standard Turing machine $M_i$ and use the wellorder that it encodes. Then we analyze the computational process of an ITTM using the ordinal that corresponds to $M_i$.

But if we want to analyze the computational process when $alpha$ is uncomputable (assuming that Infinite Time Turing Machines can clock very large uncomputable ordinals), we need to obtain a precise description of $alpha$ somewhere. But where can we find formal descriptions of such ordinals in the first place (assuming that the set of these descriptions is required to be countable)?

EDIT

This question can be formulated as follows.

Imagine the existence of an oracle that always tells the truth. Assuming that you and the oracle solve problems of

given a natural number $x$, find an ITTM that is indexed by $x$

and

given a real number $x$, decode it as an ordinal

in exactly the same way, this oracle sends the following message:

I have chosen a natural number $N$. All I can tell you is that an ITTM indexed by $N$ clocks some ordinal $alpha$. You can send me any real number that encodes any ordinal, and I will immediately tell you whether this ordinal is equal to $alpha$ or not. You have an infinite amount of infinitely powerful computational resources and infinite amount of time. Moreover, if you send me any countable set $S$ of ordinals, I will send you a number $0$ if this set does not contain $alpha$; otherwise, I will send you a positive number $i$ such that an $i$-th element of $S$ is equal to $alpha$. And here are three rules that must be taken into account: (i) any set $S$ that you send me is required to be a set of real numbers, where each element encodes an ordinal in a particular (fixed) way. It is your choice to fix such encoding, but you must tell me about your choice so that we can interpret all reals in the same way; (ii) If you send me a countable set (described in the previous rule), then (assuming that we agree on a fixed algorithm that decodes a single real number into a countable set of real numbers) you are required to provide an exact description of an algorithm (namely, an index of an ITTM together with a real number that encodes an ordinal for a stage when the output tape is expected to contain the real number that encodes the entire set $S$) that generates $S$; (iii) for any ITTM indexed by any natural number $n$, you are allowed to ask for a real number that appears on the output tape at stage $beta$, but if and only if you provide a real number that encodes an ordinal $beta$ (in the same fixed way that you have chosen). You can store these numbers in arbitrary (finite/infinite) sets/multisets and operate with them in any way you want.

So, if you find $alpha$, you win.

Question: does there exist a way to always win, no matter which $N$ the oracle chooses? If yes, then how?

It's a good question. I will describe those specific aspects of the answer which I know about (but it will be a bit long though). There are very many aspects of course, of which I don't know much about.

Specifically though, I don't know much of anything about how models like $omega$ tape ITTMs handle this (that's why I will not try to describe how they handle this issue). So I will assume a more general model (such as ORM or extended tape ITTM).

First of all, one basic principle you can observe is that if you have access to well-order relation $lessequals:mathbb{N}^2 rightarrow {0,1}$ (for a well-order of $mathbb{N}$) of order-type $alpha$ then you can use it to halt a "little above" $alpha$. More specifically, given the access to the function $lessequals$, there will be some $beta geq alpha$ such that our given program halt at time $beta$. This isn't difficult (but not obvious at first though).

Before stating the process, let me first mention that all the steps below that have been described informally can indeed be checked by a powerful enough program model. First let $address:alpha rightarrow mathbb{N}$ be the (unique) order-preserving bijection(under the well-ordering relation) from $alpha$ to $mathbb{N}$. [I am not fully sure whether that's the best way to put it formally ... someone can correct this if I am wrong]. Now we define $address_{p}:p rightarrow mathbb{N}$ (where $p leq alpha$) to denote the restriction of the address function.

Now suppose that you are given an entirely arbitrary function $f:mathbb{N} rightarrow {0,1}$. Note that we don't even have to know before-hand whether $f$ is a well-order relation (for some well-order of $mathbb{N}$). The thing is that we can do both of the following at once: (1) We can check whether $f$ codes a well-order or not. (2) If the answer to (1) is yes, then suppose $f$ codes a well-order of order-type $alpha$. Then our program will halt just above $alpha$.

The first thing that we check is whether $f$ linear order on $mathbb{N}$ (https://en.wikipedia.org/wiki/Total_order). One can observe here is that in a program-like model you can just check each individual property in about $omega$ time (and hence all three of them in about $omega cdot 3$ time).

After this the main idea is to form the function $address_p:p rightarrow mathbb{N}$ in stages, until the stage $alpha$. First let's denote $range(address_p)=A_p$ and $B_p=mathbb{N}-A_p$ for the sake of convenience/brevity. Initially we have $A_0=phi$. Our first question is: what's the value $address(0)$? We basically check all the elements in $x in B_0$ one by one. We want to check whether $f(x,y)$ is true for all elements $y in B_0(=mathbb{N})$ and furthermore check whether $f(x,z)$ is false for all elements $z in A_0(=phi)$.

Now there are two different things that could happen. (i) We can't find any $x in A_0$ which satisfies the above requirement. (ii) We can find an $x in A_0$ which satisfies the above requirement. If (i) happens to be true, then the program can simply return "the given $f$ doesn't code a well-order". If you observe a bit closely the truth of (i) implies an infinite descending chain. Now if (ii) happens to be true, then the element $a in B_0$ for which this was true we basically set $address(0)=a$ (re-call that we are building this function in stages) and $A_1=A_0 cup a$. You might object what happens if we get two different $a,b in B_0$(where $aneq b$) so that both satisfy the given condition (but this won't happen because of the condition of linear order satisfied by $f$).

Essentially the above template is what you follow through out the calculation. We have a counter variable $p$ which starts from $0$ and which we keep increasing. At any given stage we have already formed $address_{p}:p rightarrow mathbb{N}$, and hence also the sets $A_p$ and $B_p$. But the question is that when do we know when to stop?? The answer is simple, once we think about it a bit! We have to keep a check on the set $B_p$ at each value $p$. Once $B_p=phi$ we have actually formed the function $address:alpha rightarrow mathbb{N}$. In that case we stop after we observe this condition.

Note that we could also stop well before $B_p=phi$. But actually, this would ONLY happen if $f$ didn't code a well-order. If $f$ did code a well-order we would stop at some point $beta$ where $beta geq alpha$.

Finally, let me add a bit of explanation how, in a formal sense, this construction proceeds. In a formal sense, the idea is that since we have already shown $f$ to be a linear order on $mathbb{N}$, now we need to prove the lack of infinite descending sequences. And this is the main idea with the construction of the set $A_p$ in stages. In particular, for any arbitrary stage $p leq alpha$, if the program doesn't stop/halt at that stage then we can say: "There are no infinite descending sequences which use an element that belongs to $A_p$". In other words, for every infinite descending sequence $g:mathbb{N} rightarrow mathbb{N}$ [that is a function $g$ such that for all $n in mathbb{N}$, $g(n) neq g(n+1)$ and $f(g(n+1),g(n))=1$], we must have $range(g) cap A_p = phi$. We could go along and try to show this by (transfinite) induction I think.

Note that directly using construction above we can basically clock just above $omega_{CK}$. Since our model already has access to all partial recursive functions (of two variables), we first check which of these functions are total. So we basically have a set $C subseteq mathbb{N}$ which initially contains indexes for all programs which compute a function from $mathbb{N}^2$ to ${0,1}$. One by one we start picking an element $x in C$ and then try to check whether it codes a well-order or not. In either case, after we have checked that we remove that element $x$ from $C$. In this case again our main stopping/halting condition is to check $C=phi$. Some reflection will show that, in this manner, we will halt just above $omega_{CK}$. (I think one can also use an alternative method like I mentioned in one of my older questions Halting at Exact Time)

I think there could be another method in a sense. I am not really familiar with it, so I am not comfortable mentioning it in detail. Given what is mentioned in this question, one could just use the corresponding (recursive) ordering relation (right from the start of a program) to stop just beyond $omega_{CK}$. But I am simply not familiar with it so I would just stop at that.

Now coming to your main question, how do we clock above $omega^{CK}_{2}$ for example. You can basically store all pairs of the form $(x,y)$ (where $xin mathbb{N}$ and $y in omega_{CK}$) where $x$ is an index of a program coding a well-order and $y$ is the order-type of the corresponding well-order. This can just be done by using the first construction described in the answer.

Alternatively, you can also store all $(x,y)$ where $x in mathcal{O}$ and $y=|x|_mathcal{O}$. But the construction will be a bit different (basically similar to what I described in my question above).

It is obvious that we can use any of the above collections to form a well-order of $mathbb{N}$ with order-type $omega_{CK}$. But now our infinite program can easily form a collection of all ordinary programs with access to the well-order relation for $omega_{CK}$. And much in the same way as before, this can be used to stop above $omega^{CK}_{2}$ for example.

My knowledge is a quite limited so I don't know/understand the full extent. Though this can vary depending on specific model you use. You would usually find it in relevant papers though, I think.

EDIT:

As far as I can guess, what you are asking is that if $alpha$ is a clockable ordinal, then can find a function $f:mathbb{N}^2 rightarrow {0,1}$ that can serve as a well-order relation for well-order of $mathbb{N}$ with order-type $alpha$. Once again I will assume a program style model (with variables with free range) .... mostly only because of familiarity reason.

Suppose some program starting from empty state halts at stage $alpha+1$. And now we want to write the "description" of $alpha$ as a real. First we set a variable equal to $alpha$ (which we can do easily). Then we simulate all programs (not ordinary ones, the ones from our general model) from empty input (using dovetailing etc.). Observe that this kind of simulation is indeed possible. Initially set $C=mathbb{N}$. When a given program reaches stage $alpha$ without halting it is excluded/removed from the simulation (and hence from $C$). When a program with index $x in mathbb{N}$ halts at time $t<alpha$ we add the pair $(x,t)$ in some main list $L$ (and also remove $x$ from $C$).

The above routing halts when $C=phi$. Indeed the routine will halt at some point (though it needs a bit of pondering), most importantly because we don't allow any program to run for more than $alpha$ time. And once you look carefully enough, the list $L$ can be used to describe the real which codes $alpha$. For example, if $L$ included for some $beta<alpha$, three different elements $(10,beta)$,$(14,beta)$,$(18,beta)$ then we just keep $(10,beta)$. Hence we have the well-order relation for well-order of a subset of $mathbb{N}$ with order-type $alpha$. This can easily be converted to obtain the relation for a well-order of $mathbb{N}$.

To make sure that the above construction works we need to prove that whenever the code $f:mathbb{N}^2 rightarrow {0,1}$ for a well-order of order-type $alpha$ is writeable, then so is code $g:mathbb{N}^2 rightarrow {0,1}$ for a well-order of any order-type $beta<alpha$. For this, consider the program that starts from empty input and gives us $f$. Now even an ordinary program can be used to obtain $g$.