What is the full definition of the head position “inferior limits” rule for Ordinal Turing Machines?

Question

I cannot seem to find a full, unambiguous definition of the “inferior limits” rule for Ordinal Turing Machines Ordinal Turing Machines in case of how to determine the head position at limit ordinal time.

The linked source only contains the following information:

If the head is for example moving linearly towards a limit location, say $H(s_0 + i) = h_0 + i$ for $i < \lambda$, we will have $H(s_0 + \lambda) = h_0 + \lambda.$

Question: what is the full list of properties such that if a particular pair of ordinals $(\tau, t)$ satisfies all of these properties, the head position at limit ordinal time $t$ is equal to $\tau$?

Answer 1

Definition $\bf{2}$$(e)$ on page $6$ of the PDF to which you linked defines the tape content $T(t)$, state $S(t)$, and head position $H(t)$ at limit $t$. The state is the most straightforward:

$$\begin{align*} S(t)&=\liminf_{r\to t}S(r)\\ &=\lim_{r\to t}\inf_{r\le s<t}S(s)\\ &=\sup_{r<t}\inf_{r\le s<t}S(s)\,. \end{align*}$$

Recall that the states are simply natural numbers. This just says that $S(t)$ is the smallest state that occurs cofinally in the sequence $\langle S(r):r<t\rangle$, if there is one; otherwise $S(t)$ defaults to $0$.

The tape content is a binary vector with a component $T(t)_\xi$ for each ordinal $\xi$, and it is defined very similarly at limit ordinals: for each ordinal $\xi$,

$$\begin{align*} T(t)&=\liminf_{r\to t}T(r)\\ &=\lim_{r\to t}\inf_{r\le s<t}T(s)\\ &=\sup_{r<t}\inf_{r\le s<t}T(s)\,. \end{align*}$$

Because $T$ takes values in $\{0,1\}$, this boils down to saying that if the sequence $\langle T(r):r<t\rangle$ is eventually constant with value $b$, then $T(t)=b$, and otherwise $T(t)$ defaults to $0$.

Finally,

$$\begin{align*} H(t)&=\liminf_{\substack{s\to t\\S(s)=S(t)}}H(s)\\ &=\lim_{\substack{s\to t\\S(s)=S(t)}}\inf_{\substack{s\le u<t\\S(s)=S(u)}}H(u) \\&=\sup_{\substack{s<t\\S(s)=S(t)}}\inf_{\substack{s\le u<t\\S(s)=S(u)}}H(u)\,. \end{align*}$$

Here we don’t look at the entire sequence $\langle H(s):s<t\rangle$, but only at the subsequence indexed by those $s<t$ such that $S(s)=S(t)$, i.e., those times at which the machine was in the same state.

Answer 2

In infinite time, one is often is concerned with behaviour on limits. In case of OTM, the rules for "state" and "cell contents" have a relatively simple description. Consider a function $Value:\mathrm{Ord} \rightarrow n$ (for some finite ordinal $n$). Below we are really only describing a convention for determining $Value(t)$ (where $t$ is a limit). Also, in expressions below, the quantification is assumed to be over ordinals.

Suppose there is a "last time" (less than $t$) after which the function remains constant. That is, there exists some $a$ such that for all $a<b<t$ we have $Value(b)=c$, where $c$ is some constant. In that case, we always set $Value(t)=c$. But what if there is no such "last time". Meaning, for a given limit ordinal $t$, the following condition is false: $\exists a<t \,\, \forall b>a \,[\, b<t \rightarrow \exists c \,( Value(b)=c) \, ]$. If the mentioned condition is false, then we can have to describe how to evaluate $Value(t)$.

In that case, define a predicate $R:\omega \rightarrow \{0,1\}$ as: $R(x) \equiv (\forall a<t) (\exists b>a)\,[\,b<t \wedge Value(b)=x\,]$. Next define a set of finite ordinals $A$ as $A=\{x \in \omega\,|\,R(x)\,\,is\,\,true\}$. We define $Value(t)$ to be smallest value contained in the set $A$. One other thing to note is that because the range of $Value$ function is assumed to be finite, the set $A$ will always contain at least one element.

The convention described above is what "state number" and "cell contents" in OTM follow.For example (informal description of previous paragraph), denoting the program-state at some time $x$ as $S(x)$, here is how we determine $S(t)$ (for some limit ordinal $t$). Suppose the set of states is $\{0,1,2,3,4,5,.....100\}$. First check whether state-$0$ occurs for arbitrarily large ordinal values less than $t$? If it does then $S(t)=0$. It it doesn't then check whether state-$1$ occurs for arbitrarily large values less than $t$? If it does then $S(t)=1$. It it doesn't then check the same for state-$2$,$3$,$4$ and so on, until you find a value $n \leq 100$ such that state-$n$ occurs for arbitrarily large values less than $t$. In that case, we set $S(t)=n$.

---

For determining head position, denote the head position at some time $x$ as $H(x)$. I feel that it helps a bit to write the actual definition in parts. This is what I will try to do below.

First determine the value $N=S(t)$, the state-number at time $t$. Note that $N$ is just an ordinary natural number. Now form a set of ordinals $X \subseteq t$ defined by $X=\{\, x\in Ord\,|\,x<t \,\wedge \, S(x)=N \}$. Note that there are arbitrarily large ordinals $<t$ that are contained in this set $X$.

For any ordinal $n<t$ define $A(n)=min\{x \,|\,x\in X \, \wedge \, n\leq x <t\}$. And now we have: $H(t)=\sup\{A(x)|x<t\}$.

---

The above is a formal description for head position. Intuitively we can use some shortcuts in number of cases. Here is one (I might try to add one or two more later).

(1) First check whether you can find a smallest time $T<t$ such that the head position never decreases from time $T$ till time $t$. In other words, let $T$ be the smallest value such that we can say that the head position is non-decreasing in the interval $[T,t)$. In that case just set $H(t)=\sup\{H(x)\,|\,T \leq x<t\}$. If we can't find a smallest time $T$ then we just go back to definition.