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 and an example to help you.
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 Ordinals
In this section I will introduce the concept of transfinite ordinals in a somewhat informal context. If you would like to look up a more formal definition this explanation is based of of the Von Neumann definition of ordinals.
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. There are precise rules about these operators, but we will just use them as special notation without definition. 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\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z < \omega^x\})\\ \end{eqnarray} \$
If an ordinal is not the successor of another ordinal, meaning there is not a next smaller ordinal, we call that ordinal a limit ordinal. For example \$\omega\$, \$\omega\times3\$, and \$\omega^{\omega\times 2}+\omega^6\times 4\$ are all limit ordinals. \$3\$, \$\omega\times 5 + 12\$ and \$\omega^{\omega^\omega}+1\$ are not. Some authors will specify further that 0 is not a limit ordinal, we will be explicit about 0 when we talk about limit ordinals to avoid confusion.
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\$
\$\$
Example
Here we have a diagram of a long running 2-state machine:
If we want to calculate how long this takes to halt we can't just throw it into a computer and run it, rather we have to determine it by hand.
To start we follow the machine through it's normal execution. It starts at \$q_1\$ and we can see that from there it always moves to \$q_2\$ flipping the cell under the read-write head. So here it turns the cell on. Then since the cell is on it will transition back to \$q_1\$, turning the cell off and moving to the right. This puts us in the exact same condition as the start, except the read-write head has advanced by 1. So it will continue in this loop of flipping on bit on and off and moving to the right endlessly.
Now that we have determined the behavior of the machine for all finite steps we can figure out the state at step \$\omega\$. Each cell is on for at most 1 step, before being turned off, and then it is never on again. So the limit supremum of each cell is \$0\$, and at step \$\omega\$ the tape is entirely empty.
So this means that after \$\omega\$ the machine just repeats its exact behavior, the condition at step \$\omega+n\$ is the same as the condition at step \$n\$. And this persists even after we hit another limit ordinal, \$\omega+\omega\$, the tape remains blank and just repeats the same behavior over and over.
ANIMATION 2 HERE
So we now have an accurate description of the machine for states of the form \$\omega\times n + m\$, and it doesn't halt for any of those steps. It just repeats the same infinite pattern an infinite number of times. So now we can look at the step after all the steps we have described. We take the next limit ordinal:
\$ g(\{\omega\times n + m : n\in \mathbb{N}, m \in \mathbb{N}\}) = \omega\times\omega = \omega^2 \$
Your first instinct might be that the tape will be completely empty again, since it was empty at every step \$\omega\times n\$. However with infinities instincts can be misleading, so we should look at the definitions carefully instead.
In order for a cell to be zero it must converge to zero. Since the only possibilities are zero and one, this means that for each cell there must be some step \$x\$ after which that cell is always zero. Previously since each cell was only turned on once that step was just the step after it was turned off.
Now if such a step were to exist for a cell \$k\$ it would be of the form \$\omega\times n + m\$, however we know that the cell will be turned on again some time during the \$\omega\times(n+1)\$ iteration. In fact it will be turned on at exactly step \$\omega\times(n+1) + 2k + 1\$.
So no cell (with a non-negative index) will converge to a stable value. Meaning that by the limit supremum all non-negative cells will be on at time \$\omega^2\$.
ANIMATION 3 HERE
So here we finally get some new behavior. With cell 0 on, the machine transitions to \$q_2\$ turning the cell off, and since \$q_2\$ doesn't have a transition for off cells the machine halts.
This gives us a total of \$\omega^2+1\$ steps until halting.