Infinite time Turing machine

View full site to see MathJax equation

ITTM busy beaver
Growth rate	>* all ITTM-computable functions
Notations	\(\Sigma_{\infty}(n)\)
Author(s)	Jamie Long and Lee J. Stanley
Year	1998

Infinite time Turing machines (ITTMs) are a generalization of Turing machines to infinite computation lengths, first described by Joel David Hamkins and Andy Lewis. They lead to a stronger analog \(\Sigma_\infty\) to the busy beaver function.

Definition

The original model by Hamkins and Lewis has three one-sided, two-color countably infinite tapes, called input, scratch and output tapes, and a single read-write head which reads one cell from each tape. (Models with one tape have been considered as well — surprisingly, they have been shown to be weaker. To our knowledge, tapes with more than two colors have not been explored.) The transition table takes into account (but not necessarily behaves in the same way) all three tapes simultaneously, and writes three at once. The scratch and output tapes are blank initially, and the input tape contains the input to the machine.

ITTMs have a particular state marked as the limit state. At each step, the ITTM proceeds normally with a timer \(t\) starting at zero and incrementing at each step. If it does not halt for any \(t < \omega\), at \(t = \omega\) each cell on each tape is set to the limit superior of that cell's symbol for steps \(t = 0, 1, 2, \ldots\). In addition, the head is set to the leftmost position and the state is set to limit. The ITTM continues as before, and if it continues to \(t = \omega2\) without halting, the same thing happens with the limit superior of the tapes for \(t = \omega, \omega + 1, \omega + 2, \ldots\). In general, if the ITTM reaches a countable limit ordinal \(\alpha\) without halting, at time \(t = \alpha\), it is set to the limit superior of the tapes at \(t = \beta\) for all \(\beta < \alpha\). That is, a cell is set to 1 iff for all \(\beta < \alpha\), there is some step \(\beta < \gamma < \alpha\) such that the cell was set to 1 at step \(t = \gamma\).

If the ITTM halts, the contents of the output tape at halting time are the output of the machine. If the ITTM does not halt, but after some point the output tape never changes, the output tape after that point is the eventual output of the machine. For both halting and non-halting cases, all of the configurations of the three tapes over the lifetime of the ITTM are the accidental outputs of the machine. It should be noted that outputs and eventual outputs are unique if they exist, but accidental outputs are not.

Formal definition

Formally, a two-color ITTM is a 5-tuple \(M = (Q, \delta, q_0, q_H, q_L)\) with the following components:

• \(Q\) is a finite, non-empty set of states.
• \(q_0 \in Q\) is the initial state.
• \(q_H \in Q\) is the halting state.
• \(q_L \in Q\) is the limit state.
• \(\delta : (Q \backslash \{q_H\}) \times \{0, 1\}^3 \rightarrow Q \times \{0, 1\}^3 \times \{L, R\}\) is the transition table. Each production has a non-halting state and three colors mapping to a state, three colors, and a movement.

Most definitions of the standard TM have a symbol designated as "blank," which is the only symbol that can appear infinitely many times on tape. ITTMs have no such restriction, since ITTM inputs and outputs can be infinitely large.

Configurations

This section defines configurations of the machine and how state transitions work. The semantics defined in this section are identical to those of an ordinary machine (albeit with three tapes).

A configuration of \(M\) is a 3-tuple \((p, \tau, m)\) where \(p \in Q\) is the current state of the machine, \(\tau : (\mathbb{N}\times\{0,1,2\}) \rightarrow \{0, 1\}\) are the contents of tapes, and \(m \in \mathbb{N}\) is the positions of the head. We use \(C(M)\) to denote the set of configurations. We define \(\leadsto\) (a single computation step) as a binary relation over \(C(M)\) as follows. We say that \((p, \tau, m) \leadsto (p', \tau', m')\) iff the following are true:

• \(\delta(p, (\tau(m,0),\tau(m,1),\tau(m,2))) = (p', (c_0,c_1,c_2), \Delta m)\).
• For all \(n \in \mathbb{N},i\in\{0,1,2\}\), \(\tau'(n,i) = \left\{ \begin{array}{lr} c_i & : n = m\\ \tau(n,i) & \text{otherwise} \end{array} \right.\).
• \(m' = \left\{ \begin{array}{lr} m + 1 & : \Delta m = R \\ \max\{m - 1, 0\} & : \Delta m = L \end{array} \right.\)

It can be seen that \(\leadsto\) is a function. That is, \((p', \tau', m')\) is unique.

Input, output, and evolution

An input to an ITTM is simply a function \(I:\mathbb{N} \rightarrow \{0, 1\}\) (meant to be the content of the first tape), and an initial contents for that input is \(\tau_0:\mathbb{N}\times\{0,1,2\} \rightarrow \{0,1\}\) such that \(\tau_0(n,0)=I(n),\tau_0(n,1)=\tau_0(n,2)=0\). A computation of \(M\) on an input \(I\) is a function \(U : \mu \rightarrow C(M)\) (where \(\mu\) is a successor ordinal, or the class \(\text{On}\)) that satisfies the following properties:

• \(U(0) = (q_0, \tau_0, 0)\)
• For all \(\alpha + 1 \in \mu\), \(U(\alpha) \leadsto U(\alpha + 1)\).
• For all limit ordinals \(\alpha \in \mu\), \(U(\alpha) = (q_L, \tau_\alpha, 0)\) where for all \(i \in \mathbb{N}\times\{0,1,2\}\), \(\tau_\alpha(i) = \text{lim sup} _{\beta < \alpha} \tau_\beta(i)\) where \(U(\beta) = (\bullet, \tau_\beta, \bullet)\).
• If \(\mu \neq \text{On}\), \(U(\mu - 1) = (q_H, \bullet, \bullet)\).

Halting, writing, and ITTM-computability

If \(\mu\neq\text{On}\), then the machine is halting for \(\tau_0\), and we call \(\mu\) the halting time. Define the output of the computation as the function \(H:\mathbb{N} \rightarrow \{0,1\}\), defined as \(H(n) = \tau_{\mu-1}(n,2)\). It is not hard to show that this output must be unique.

If \(\mu = \text{On}\), then the machine is nonhalting for \(\tau_0\). If there is some \(H : \mathbb{N} \rightarrow \{0,1\}\) such that for all sufficiently large \(\alpha\), \(\forall n : \tau_\alpha(n,2) = H(n)\), then we say that the machine eventually writes \(H\). It is not hard to show that eventual output is also unique if it exists.

For all \(H : \mathbb{N} \rightarrow \{0,1\}\), if there is an \(\alpha \in \mu, i \in \{0, 1, 2\}\) such that \(\forall n: \tau_\alpha(n, i) = H(n)\), we say that the machine accidentally writes \(H\) for the input. Accidental outputs are not unique.

The uniqueness of outputs and eventual outputs allows us to define the partial ITTM-computable functions and partial eventually-computable functions. A partial function \(f : \mathbb{N} \rightarrow \mathbb{N}\) is ITTM-computable iff there exists an ITTM \(M\) such that \(f(n) = m\) iff \(M\) produces output \(m\) with input \(n\) (using an encoding scheme for natural numbers such as \(\underbrace{11...1}_{n}00...\)). A partial function \(f : \mathbb{N} \rightarrow \mathbb{N}\) is eventually computable iff there exists an ITTM \(M\) such that \(f(n) = m\) iff \(M\) produces eventual output \(m\) with input \(n\).

\(\Sigma_\infty\)

Long and Stanley proposed an infinite time Turing machine busy beaver function \(\Sigma_\infty(n)\). It is defined as the maximal finite output \(k\) of an ITTM with at most \(n\) non-halting non-limit states given blank input, where they define output to be a natural number \(k\) if it is of the form \(\underbrace{11...1}_{k}00...\).

They have shown that \(\Sigma_\infty\) eventually dominates every ITTM-computable function, in analogy to domination property of \(\Sigma\) function. Therefore, it is an uncomputably fast-growing function.

ITTM ordinals

ITTMs are capable of producing far more outputs than ordinary TMs, including ordinals. This leads to several classes of ordinals:

• An ordinal \(\alpha\) is writable iff an ITTM with empty input (all zeros) has \(\alpha\) as its output.
• An ordinal \(\alpha\) is clockable iff an ITTM with empty input halts at time \(\alpha\).
• An ordinal \(\alpha\) is eventually writable iff an ITTM with empty input has \(\alpha\) as its eventual output.
• An ordinal \(\alpha\) is accidentally writable iff an ITTM with empty input has \(\alpha\) as an accidental output.

(The first and last two definitions can apply to many mathematical objects other than ordinals) These definitions give rise to several large countable ordinals (the infinite time Turing machine ordinals):

• \(\lambda\), the supremum of all writable ordinals
• \(\gamma\), the supremum of all clockable ordinals
• \(\zeta\), the supremum of all eventually writable ordinals
• \(\Sigma\), the supremum of all accidentally writable ordinals

It has been shown that \(\omega_1^\text{CK} \ll \lambda = \gamma < \zeta < \Sigma\).

Encoding ordinals in bitstrings

To be able to read and write ITTM ordinals, we must specify an encoding scheme to represent ordinals with countably infinite bitstrings. Here is one such scheme:

• "1000..." encodes \(0\).
• If string S encodes \(\alpha\), then the string "0" + S (where + denotes string concatenation) encodes \(\alpha + 1\).
• If strings \(S_0,S_1,S_2,\ldots\) encode \(\alpha_0,\alpha_1,\alpha_2,\ldots\), then we interleave the strings into a new bitstring \(T\) according to the following scheme:
  • Start with every bit of \(T\) labeled "empty".
  • Write the bits of \(S_0\) in every second bit of \(T\).
  • Write the bits of \(S_1\) in every second remaining empty bit of \(T\).
  • Write the bits of \(S_2\) in every second remaining empty bit of \(T\).
  • Repeat for all of the \(S_i\).
  • Write "1" in the first bit of \(T\).
  • \(T\) encodes \(\sup\{\alpha_i\}\).

Using this encoding, "\(\color{red}{01000...}\)" represents 1, "\(\color{blue}{001000...}\)" represents 2, "\(\color{green}{0001000...}\)" represents 3 and so on.

Then \(1\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{1}\) \(\color{green}{0}\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{0}\) \(0\) \(\color{red}{0}\) \(\color{blue}{1}\) \(\color{red}{0}\) \(\color{green}{0}\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{0}\) \(0\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{0}\) \(\color{green}{0}\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{0}\) \(0\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{0}\) \(\color{green}{1}\) \(\color{red}{0}\) \(\color{blue}{0}\) \(\color{red}{0}\) \(0\) \(\ldots\) represents \(\omega\).

This is of course one of many possible encoding schemes, and within this scheme multiple bitstrings represent a single ordinal.

Klev's \(\mathcal{O}^+\)

Ansten Mørch Klev extended Kleene's \(\mathcal{O}\) to the set of all writable ordinals. Let \(f_0, f_1, f_2, \ldots\) be an enumeration of all ITTM-computable partial functions (where the output of an ITTM is based on the tape when it halts). The rules are otherwise identical to Kleene's \(\mathcal{O}\):

• \(0 \in K\) and \(\mathcal{O}^+(0) = 0\).
• If \(n \in K\) and \(\mathcal{O}^+(n) = \alpha\), then \(2^n \in K\), \(\mathcal{O}^+(2^n) = \alpha + 1\), and \(n <_{\mathcal{O}^+} 2^n\).
• If for all natural numbers \(n\), we have \(f_i(n) \in K\) and \(f_i(n) <_{\mathcal{O}^+} f_i(n + 1)\), then \(3 \cdot 5^i \in K\), \(\mathcal{O}^+(3 \cdot 5^i) = \lim_{k \rightarrow \omega} \mathcal{O}^+(f_i(k))\), and for all \(k\) \(f_i(k) <_{\mathcal{O}^+} 3 \cdot 5^i\).
• \(a <_{\mathcal{O}^+} b\) and \(b <_{\mathcal{O}^+} c\) implies \(a <_{\mathcal{O}^+} c\).

\(\mathcal{O}^+\) is capable of expressing all ordinals \(< \lambda\) (all writable ordinals).

Klev's \(\mathcal{O}^{++}\)

In the same paper, Klev introduced \(\mathcal{O}^{++}\), which has \(f_i\) enumerates all eventually computable partial functions (that is, the output of an ITTM is based on what the tape converges to). The rules are otherwise identical:

• \(0 \in K\) and \(\mathcal{O}^{++}(0) = 0\).
• If \(n \in K\) and \(\mathcal{O}^{++}(n) = \alpha\), then \(2^n \in K\), \(\mathcal{O}^{++}(2^n) = \alpha + 1\), and \(n <_{\mathcal{O}^{++}} 2^n\).
• If for all natural numbers \(n\), we have \(f_i(n) \in K\) and \(f_i(n) <_{\mathcal{O}^{++}} f_i(n + 1)\), then \(3 \cdot 5^i \in K\), \(\mathcal{O}^{++}(3 \cdot 5^i) = \lim_{k \rightarrow \omega} \mathcal{O}^{++}(f_i(k))\), and for all \(k\) \(f_i(k) <_{\mathcal{O}^{++}} 3 \cdot 5^i\).
• \(a <_{\mathcal{O}^{++}} b\) and \(b <_{\mathcal{O}^{++}} c\) implies \(a <_{\mathcal{O}^{++}} c\).

It is capable of expressing all ordinals \(< \zeta\) (all eventually writable ordinals)

It is worth noting that the concepts of \(\mathcal{O}^+\) and \(\mathcal{O}^{++}\) cannot be extended to all accidentally writable ordinals, because many ITTMs accidentally write more than one ordinal. Indeed, there exist "universal" ITTMs accidentally writing all accidentally writable ordinals. No ordinal notation is known that specifically targets all ordinals \(< \Sigma\).

Fundamental sequences

It is possible to define a system of fundamental sequences associated to all ordinals \(< \lambda\) and \(< \zeta\):

For each \(\alpha < \lambda\), if \(\alpha\) is a limit ordinal, then \(\alpha[n]\) is defined as \(\mathcal{O}^+(f_{i_{\alpha}}(n))\), where \(i_{\alpha}\) denotes the minimum of the non-empty set \(\{i \in K \mid \mathcal{O}^+(i) = \alpha\}\).

Define \(g(0) = 0\) and \(g(n+1)\) as the notation with smallest \(m \in \mathbb{N}\) such that \(m \in K\) and \(\mathcal{O}^+(g(n)) < \mathcal{O}^+(m)\). The fundamental sequence for \(\lambda\), then, is defined as \(\lambda[n] = \mathcal{O}^+(g(n))\).

Analogously, for each \(\alpha < \zeta\), if \(\alpha\) is a limit ordinal, then \(\alpha[n]\) is defined as \(\mathcal{O}^{++}(f_{i_{\alpha}}(n))\), where \(i_{\alpha}\) denotes the minimum of the non-empty set \(\{i \in K \mid \mathcal{O}^{++}(i) = \alpha\}\).

Define \(h(0) = 0\) and \(h(n+1)\) as the notation with smallest \(m \in \mathbb{N}\) such that \(m \in K\) and \(\mathcal{O}^{++}(g(n)) < \mathcal{O}^{++}(m)\). The fundamental sequence for \(\zeta\), then, is defined as \(\zeta[n] = \mathcal{O}^{++}(h(n))\).

The growth rates of functions \(f_\lambda(n)\) and \(f_\zeta(n)\) under this system are supposedly slower than Rayo's function. It is not known how they compare with \(\Sigma_\infty\).

See also

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Large numbers in computers

Main article: Numbers in computer arithmetic

127 · 128 · 256 · 32767 · 32768 · 65536 · 2147483647 · 4294967296 · 9007199254740991 · 9223372036854775807 · FRACTRAN catalogue numbers
Bignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion

Uncomputable numbers

Busy beaver numbers (based on Turing theories): \(\Sigma(1919)\) (1919th busy beaver number) · Fish number 4 · \(\Xi(10^6)\) · \(\Sigma_{\infty}(10^9)\)
Rayo's numbers (based on Set theories): Rayo's number (Rayo(10¹⁰⁰)) · Fish number 7 · BIG FOOT (FOOT¹⁰(10¹⁰⁰)) · Little Bigeddon · Sasquatch · Large Number Garden Number
Miscellany: Hollom's number · Oblivion · Utter Oblivion · (Ultimate Oblivion)