13
\$\begingroup\$

Challenge Statement

The goal of this challenge is to build the 5 state Infinite Time Turing Machine that takes the longest to halt. Since Infinite Time Turing Machines can run for infinite time your score will be a "transfinite ordinal".

That's the challenge statement, but if you don't what all this means or want to dig into the details the rest of this challenge is some definitions and an example to help you. If there is something you don't understand or that isn't explained feel free to leave a comment.

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:

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.

2-state machine finite behavior

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.

Omega behavior of the 2-state machine

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\$.

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.

\$\endgroup\$
0

1 Answer 1

9
\$\begingroup\$

5 states, \$\omega^{\omega\cdot2}+\omega\cdot2+1\$

State Tape Next State Write Move
Init 0 Lseek 1 Left
Init 1 Rtest 0 Left
Lseek 0 Rseek 1 No
Lseek 1 Lseek 1 Left
Rtest 0 Halt - -
Rtest 1 Rseek 0 Right
Rseek 0 Lclear 1 No
Rseek 1 Rseek 0 Right
Lclear - Lclear 0 Left

Visualization

# 0
      |
...00000000...
      ▲ Init
...00010000...
     ▲ Lseek
...00110000...
     ▲ Rseek
...00010000...
      ▲ Rseek
...00000000...
       ▲ Rseek
...00001000...
       ▲ Lclear
...00000000...
      ▲ Lclear
.
.
.
# omega
      |
...00000000...
      ▲ Init
.
.
.
# omega*2
      |
...00000000...
      ▲ Init
.
.
.
# omega^2
      |
...00111000...
      ▲ Init
...00101000...
       ▲ Rtest
...00100000...
        ▲ Rseek
...00100100...
        ▲ Lclear
...00100000...
       ▲ Lclear
...00100000...
      ▲ Lclear
...00100000...
     ▲ Lclear
...00000000...
    ▲ Lclear
.
.
.
# omega^3
      |
...00111100...
      ▲ Init
.
.
.
# omega^4
      |
...00111110...
      ▲ Init
.
.
.
# omega^omega
      |
...00111111...
      ▲ Init
...00101111...
       ▲ Rtest
...00100111...
        ▲ Rseek
.
.
.
# omega^omega+omega
      |
...00100000...
      ▲ Init
...00110000...
     ▲ Lseek
...00110000...
    ▲ Lseek
...01110000...
    ▲ Rseek
...00110000...
     ▲ Rseek
...00010000...
      ▲ Rseek
...00000000...
       ▲ Rseek
...00001000...
       ▲ Lclear
...00000000...
      ▲ Lclear
.
.
.
# omega^omega*omega == omega^(omega+1)
       |
...001111111...
       ▲ Init
...001101111...
        ▲ Rtest
.
.
.
# omega^(omega+1) + omega
       |
...001100000...
       ▲ Init
.
.
.
# omega^(omega*2)
       |
...111111111...
       ▲ Init
.
.
.
# omega^(omega*2) + omega
       |
...111100000...
       ▲ Init
...111110000...
      ▲ Lseek
...111110000...
     ▲ Lseek
.
.
.
# omega^(omega*2)+ omega*2
       |
...111110000...
       ▲ Init
...111100000...
        ▲ Rtest
HALT

4 states, \$\omega^\omega+\omega+1\$

State Tape Next State Write Move
Init 0 Ltest 1 Left
Init 1 Rseek 0 Left
Ltest 0 Rseek 1 Right
Ltest 1 Halt - -
Rseek 0 Lclear 1 No
Rseek 1 Rseek 0 Right
Lclear - Lclear 0 Left

Visualization

      |
...00000000...
      ▲ Init
...00010000...
     ▲ Ltest
...00110000...
      ▲ Rseek
...00100000...
       ▲ Rseek
...00101000...
       ▲ Lclear
...00100000...
      ▲ Lclear
...00100000...
     ▲ Lclear
...00000000...
    ▲ Lclear
.
.
.
# Omega
      |
...00000000...
      ▲ Init
.
.
.
# Omega*2
      |
...00000000...
      ▲ Init
.
.
.
# Omega*Omega
      |
...00111000...
      ▲ Init
...00101000...
       ▲ Rseek
...00100000...
        ▲ Rseek
...00100100...
        ▲ Lclear
...00100000...
       ▲ Lclear
...00100000...
      ▲ Lclear
...00100000...
     ▲ Lclear
...00000000...
    ▲ Lclear
.
.
.
# Omega*Omega + Omega
      |
...00000000...
      ▲ Init
.
.
.
# Omega*Omega*2
      |
...00111000...
      ▲ Init
.
.
.
# Omega*Omega*3
      |
...00111000...
      ▲ Init
.
.
.
# Omega*Omega*Omega
      |
...00111100...
      ▲ Init
...00101100...
       ▲ Rseek
...00100100...
        ▲ Rseek
...00100000...
         ▲ Rseek
...00100010...
         ▲ Lclear
...00100000...
        ▲ Lclear
...00100000...
       ▲ Lclear
...00100000...
      ▲ Lclear
...00100000...
     ▲ Lclear
...00000000...
    ▲ Lclear
.
.
.
# Omega^Omega
      |
...00111111...
      ▲ Init
...00101111...
       ▲ Rseek
...00100111...
        ▲ Rseek
...00100011...
         ▲ Rseek
...00100001...
          ▲ Rseek
.
.
.
# Omega^Omega + Omega
      |
...00100000...
      ▲ Init
...00100000...
     ▲ Ltest
HALT
\$\endgroup\$
4
  • \$\begingroup\$ im confused what this even means lmao \$\endgroup\$
    – DialFrost
    Jan 29, 2022 at 23:40
  • \$\begingroup\$ what happens if no one even answers the question though? \$\endgroup\$
    – DialFrost
    Jan 31, 2022 at 5:54
  • 1
    \$\begingroup\$ @DialFrost then the 250 reputation just disappears \$\endgroup\$
    – AnttiP
    Jan 31, 2022 at 18:00
  • \$\begingroup\$ I just got a chance to check over this and your 4 state machine is pretty much exactly the same as my 4 state champ. The only difference is we have opposite handedness, i.e. all of your left movements are right in my machine and vice versa. \$\endgroup\$
    – Wheat Wizard
    Feb 9, 2022 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.