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

無限時間チューリングマシン (ITTM) はチューリングマシンの無限の計算長さへの一般化である。Joel David と Andy Lewis が最初に記述した。ビジービーバー関数をより強くして \(\Sigma_\infty\) とした。

定義

Hamkins とLewis によるオリジナルのモデルは、入力テープ、スクラッチテープ、出力テープと呼ばれる片方向で２色で無限の３つのテープを持ち、１つの読み書きヘッドを持ち、その読み書きヘッドは各々のテープから１つのセルを読む。（ひとつのテープを持つモデルも検討されたが、驚いたことにそれらは弱いことが示された。 知りうる中では２色より色が多いテープは調査されていない。）遷移表は、全ての３色が同時に考慮され、一度に３つの書き込みがなされる。スクラッチと出力のテープは始め空白で、入力テープはマシンへのインプットを持っている。

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 の定義は無限の長さの時間(?=infinitely many times)に現れ得る唯一の記号である空白を示す記号を持つが、ITTM はそのような制限はなく、ITTM の入力と出力は無限に長い。

構造

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

\(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\) は 書き込み可能 である。
• 空の入力を持つ ITTM が時刻 \(\alpha\) で停まる時かつその時に限り、\(\alpha\) は 記録可能 である。
• 空の入力を持つ ITTM が順序数 \(\alpha\) を最終出力に持つ時かつその時に限り、\(\alpha\) は 最終書き込み可能 である。
• 空の入力を持つ ITTM が順序数 \(\alpha\) を臨時出力に持つ時かつその時に限り、\(\alpha\) は 臨時書き込み可能 である。

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

• \(\lambda\) は全ての書き込み可能順序数の上限である。
• \(\gamma\), は全ての記録可能順序数の上限である。
• \(\zeta\), は全ての最終書き込み可能順序数の上限である。
• \(\Sigma\), は全ての臨時書き込み可能順序数の上限である。

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