無限時間チューリングマシン

無限時間チューリングマシン (infinite time Turing machine, ITTM) は、チューリングマシンの計算の長さを無限へ一般化したものである。ハムキンズとルイスが最初に定義した。ITTMに対するビジービーバー関数 \(\Sigma_\infty\) は通常のビジービーバー関数よりも速く増大する。

定義

以下ではハムキンズとルイスによるオリジナルの定義ではなく、 \((\alpha,\beta)\)-チューリングマシンという一般化された形で述べよう。ここで \(\alpha,\beta\) は順序数か、順序数全体のクラス \(\mathrm{On}\) である。大雑把に言えば \(\alpha\) は空間的制約、すなわちチューリングマシンのテープの長さに対する制限であり、\(\beta\) は時間的制約を表している。特に \(\alpha=\omega,\beta=\omega\) のとき普通のチューリングマシンで、\(\alpha=\omega,\beta=\mathrm{On}\) のときが無限時間チューリングマシンとなる。

\((\alpha,\beta)\)-チューリングマシンは、入力テープ、スクラッチテープ、出力テープと呼ばれる順序数 \(\alpha\) を長さとして持つ３つのテープ、１つの読み書きヘッドを持ち、その読み書きヘッドは各々のテープから１つのセルを読む。（ひとつのテープを持つモデルも検討されたが、驚くべきことにそれらは弱いことが示された）。遷移表は、３つ全てのテープの色が同時に考慮され、一度に３つの書き込みがなされる。スクラッチと出力のテープは始め空白で、入力テープはマシンへの入力を持っている。

ITTM は「極限」と記された特別な状態を持つ。ITTM は、通常は 0 から始まり、各ステップでインクリメントするタイマー \(t\) を進ませていく。もし ITTM が全ての \(t < \omega\) で停止しなければ、\(t = \omega\) にて、各テープの各セルはそのセルの記号のステップ \(t = 0, 1, 2, \ldots\) における上極限が書かれる。また、ヘッドは左端の場所に移動され、状態は「極限」状態にセットされる。ITTM がまた同じように動き続け \(t = \omega2\) まで停止せずに続けば、また同じことが起こり、\(t = \omega, \omega + 1, \omega + 2, \ldots\) におけるテープの上極限が書かれる。一般的に、ITTM が止まらずに時刻 \(t = \alpha\) で可算極限順序数 \(\alpha\) に達したら ITTM は全ての \(\beta < \alpha\) における \(t = \beta\) についての上極限が書かれる。つまり、ひとつのセルは、全ての \(\beta < \alpha\) の中で、ステップ \(t = \gamma\) で１が書かれるような \(\beta < \gamma < \alpha\) となるステップがある時かつその時に限り、１が書かれる。

もし ITTM が止まれば、停止した時刻での出力テープの中身がマシンの出力となる。もし ITTM が止まらなくても、ある点の以後出力テープが変化しない場合は、その後の出力テープは、マシンの最終出力と呼ばれる。この２つの停止する場合と停止しない場合の ITTM の履歴全ての３テープの状態は、臨時出力と呼ばれる。出力と最終出力はもし存在すればそれらは唯一であるが、臨時出力は唯一とは限らないことが言える。

正確な定義

2-状態 ITTM の正確な定義は、\(M = (Q, \delta, q_0, q_H, q_L)\) という5組であり、その要素は次のように定められる。

• \(Q\) は状態の集合で、空集合ではない有限集合である。
• \(q_0 \in Q\) は初期状態である。
• \(q_H \in Q\) は停止状態である。
• \(q_L \in Q\) は極限状態である。
• \(\delta : (Q \backslash \{q_H\}) \times \{0, 1\}^3 \rightarrow Q \times \{0, 1\}^3 \times \{L, R\}\) は遷移表であり、「停止状態以外の状態・３つのテープの色」から「状態・３つのテープの色・移動情報」への写像からなる。

通常の TM の定義には、ほとんどの場合空白という記号があり、これがテープに無限回あらわれ得る唯一の記号である。ITTMの入力と出力は無限に長いため、そのような制限（無限回あらわれる記号が唯一であるという制限）はない。

計算状況 (Configuration)

ここではマシンの計算状況と状態遷移がどのように働くかを明らかにする。このセクションで明らかになる意味論は通常のマシンの計算状況と同じである（たとえそれが３テープであっても）。

\(M\) の 計算状況 とは \(p \in Q\) が現在のマシンの状態となる３つ組 \((p, \tau, m)\) のことであり、\(\tau : (\mathbb{N}\times\{0,1,2\}) \rightarrow \{0, 1\}\) がテープの中身であり、\(m \in \mathbb{N}\) がヘッドの位置である。\(C(M)\) は計算状況の集合を表すために使う。\(C(M)\) の二項関係 \(\leadsto\) （単一の計算ステップ） を次のように定義する。\((p, \tau, m) \leadsto (p', \tau', m')\) の時かつその時に限り下記は真である:

• \(\delta(p, (\tau(m,0),\tau(m,1),\tau(m,2))) = (p', (c_0,c_1,c_2), \Delta m)\).
• 全ての \(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.\)

\(\leadsto\) は関数とみなせる。つまり、 \((p', \tau', m')\) は唯一である。

入力、出力、進化

ITTM への入力は、単純に関数 \(I:\mathbb{N} \rightarrow \{0, 1\}\) （１番目のテープの内容）であり、初期内容であるため、\(\tau_0(n,0)=I(n),\tau_0(n,1)=\tau_0(n,2)=0\) を満たす \(\tau_0:\mathbb{N}\times\{0,1,2\} \rightarrow \{0,1\}\) となる。 \(I\) における \(M\) の 計算は関数 \(U : \mu \rightarrow C(M)\) (\(\mu\) は後続順序数かクラス(\(\text{On}\)) であり、下記の性質を満たす:

• \(U(0) = (q_0, \tau_0, 0)\)
• 全ての \(\alpha + 1 \in \mu\) について、 \(U(\alpha) \leadsto U(\alpha + 1)\).
• 全ての極限順序数 \(\alpha \in \mu\) について、 \(U(\alpha) = (q_L, \tau_\alpha, 0)\) where 全ての \(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)\).
• もし \(\mu \neq \text{On}\) なら \(U(\mu - 1) = (q_H, \bullet, \bullet)\).

停止と書き込みと ITTM 計算可能性

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 propose an infinite time Turing machine busy beaver function. \(\Sigma_\infty(n)\) 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 順序数

ITTM は順序数を含む通常の TM よりもはるかにたくさんの出力を出せる点で優れている。これらにより、いくつかの順序数のクラスが導かれる:

• 空（全てゼロ）の入力を持つ ITTM が順序数 \(\alpha\) を出力に持つ場合、かつその場合に限り、\(\alpha\) は writable である。
• 空の入力を持つ ITTM が時刻 \(\alpha\) で停まる場合、かつその場合に限り、\(\alpha\) は clockable である。
• 空の入力を持つ ITTM の計算停止時にテープに順序数 \(\alpha\) が書かれている場合、かつその場合に限り、\(\alpha\) は eventually writable である。
• 空の入力を持つ ITTM の計算途中にテープに１度でも順序数 \(\alpha\) が書かれることがある場合、かつその場合に限り、\(\alpha\) は accidentally writable である。

(始めと最後の２つの定義は順序数だけでなくたくさんの数学オブジェクトに適用できる。これらの定義はいくつかの大きな可算順序数を作ることができる（無限時間チューリングマシン順序数）)

• \(\lambda\) は全ての writable な順序数の上限である。
• \(\gamma\), は全ての clockable 順序数の上限である。
• \(\zeta\), は全ての eventually writable 順序数の上限である。
• \(\Sigma\), は全ての accidentally writable 順序数の上限である。

\(\omega_1^\text{CK} \ll \lambda = \gamma < \zeta < \Sigma\) が成り立つことが示されている。

順序数のビット文字列へのコード化

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\}\).

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

Klev の表記

Ansten Mørch Klev developed two ordinal notations, \(\mathcal{O}^+\) and \(\mathcal{O}^{++}\), which express all writable and eventually writable ordinals, respectively. They are exactly the same as Kleene's \(\mathcal{O}\) but with analogous sets replacing the set of partial recursive functions.