Challenge Statement
The goal of this challenge is to build the 5 state Infinite Time Turing machine that takes the longest to halt.
The rest of this challenge is some definitions to help you.
Infinite Ordinals
In this section I will introduce the concept of transfinite ordinals in a somewhat informal context. This explanation is based of of the VonNeumann definition of ordinals if you would like to look up a more formal definition. In most contexts when talking about the order of events we use natural numbers. We can assign numbers to events such that events with smaller numbers happen earlier. However in this challenge we will care about events that happen after an infinite number of prior events, and for this natural numbers fail. So we will introduce infinite ordinals.
To do this we will use a special function \$g\$. The \$g\$ function takes a set of numbers and gives us the smallest number greater than all the numbers in that set. For a finite set of natural numbers this is just the maximum plus 1. However this function is not defined on natural numbers alone. For example what is \$g(\mathbb{N})\$, or the smallest number greater than all naturals. To create our ordinals we say
- \$0\$ exists and is an ordinal.
- If \$X\$ is a set of ordinals then \$g(X)\$ exists and is an ordinal.
This gives us the natural numbers (e.g. \$1 = g(\{0\})\$, \$2 = g(\{1\})\$ etc.) but also gives us numbers beyond that. For example \$g(\mathbb{N})\$, this is the smallest infinite ordinal, and we will call it \$\omega\$ for short. And there are ordinals after it, for example \$g(\{\omega\})\$ which we will call \$\omega + 1\$.
We will in general use some math symbols \$+\$, \$\times\$ etc. in ways that are not defined explicitly. Hopefully their use should be clear though. Here are a few specific ordinals to help you out:
\$ \begin{eqnarray} \omega\times 2 &=& \omega+\omega &=& g(\{\omega + x : x\in \mathbb{N}\})\\ \omega^2 &=& \omega\times\omega &=& g(\{\omega \times x + y : x\in \mathbb{N}, y\in \mathbb{N}\})\\ \omega^3 &=& \omega\times\omega\times\omega &=& g(\{\omega^2\times x+\omega\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z\in \mathbb{N}\})\\ \omega^\omega &=& & & g(\{\omega^x : x\in \mathbb{N}\})\\ \end{eqnarray} \$
Turing Machines
For clarity we will define the Turing machines as used for this problem. This is going to be rather formal. If you are familiar with Turing machines this is a single-tape, binary Turing machine, without an explicit halt state, and with the possibility of a no shift move. But for the sake of absolute clarity here is how we will define a classical Turing machine and its execution:
A Turing machine consists of a \$3\$-Tuple containing the following:
- \$Q\$: A finite non-empty set of states.
- \$q_s : Q\$: The initial state.
- \$\delta : Q\times \{0,1\} \nrightarrow Q\times \{0,1\}\times\{1, 0, -1\}\$: A partial transition function, which maps a state and a binary symbol, to a state, a binary symbol and a direction (left, right or no movement).
During execution of a specific Turing machine the machine has a condition which is a \$3\$-Tuple of the following:
- \$\xi_\alpha : \mathbb{Z}\rightarrow \{0,1\}\$: The tape represented by a function from an integer to a binary symbol.
- \$k_\alpha :\mathbb{Z}\$: The location of the read head.
- \$q_\alpha : Q\$: The current state.
For a Turing machine the transition function takes the condition of a machine at step \$\alpha\$ and tells us the state of the machine at step \$\alpha + 1\$. This is done using the transition function \$\delta\$. We call the function \$\delta\$ with the current state and the symbol under the read head:
\$ \delta\left(q_\alpha, \xi_\alpha\left(k_\alpha\right)\right) \$
If this does not yield a result, then we consider the machine to have halted at step \$\alpha\$, and the condition remains the same. If it does yield a result \$\left(q_\delta, s_\delta, m_\delta\right)\$ then the new state at \$\alpha+1\$ is as follows:
- \$\xi_{\alpha+1}(k) = \begin{cases}s_\delta & k = k_\alpha \\ \xi_\alpha(k) & k \neq k_\alpha\end{cases}\$ (That is the tape replaces the symbol at the read head with the symbol given by \$\delta\$)
- \$k_{\alpha+1} = k_\alpha+m_\delta\$ (That is the read head moves left right or not at all)
- \$q_{\alpha+1} = q_\delta\$ (That is the new state is the state given by \$\delta\$)
Additionally we define the condition of the machine at time \$0\$.
- \$\xi_0(k)=0\$ (Tape is all zeros to start)
- \$k_0=0\$ (Read head starts a zero)
- \$q_0=q_s\$ (Start in the initial state)
And thus by induction the state of a Turing machine is defined for all steps corresponding to a natural number.
Infinite Time Turing Machines
A classical Turing machine is equipped with a start status, and a way to get from one status to another. This allows you to determine the status of the machine at any finite step.
Infinite time Turing machines extend classical Turing machines to have a defined status non-zero limit ordinals as well. That is ordinals as defined above which are not the successor of any previous ordinal. This addition makes the condition of the machine defined at transfinite time as well.
Formal definition
For this we add an additional object to the machine's definition
- \$q_l : Q\$: The limit state
And we define the condition of the machine at some limit ordinal \$\lambda\$ to be
- \$\xi_\lambda(k) = \limsup_{n\rightarrow \lambda} \xi_n(k)\$
- \$k_n = 0\$
- \$q_n = q_l\$