FANDOM


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

定義

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

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\) で1が書かれるような \(\beta < \gamma < \alpha\) となるステップがある時かつその時に限り、1が書かれる。

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

正確な定義

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\}\) は遷移表であり、「停止状態以外の状態・3つのテープの色」から「状態・3つのテープの色・移動情報」への写像からなる。

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

構造(Configuration)

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

\(M\) のひとつの「構造」は \(p \in Q\) が現在のマシンの状態となる3つ組 \((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\}\) (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)\).[3]
  • もし \(\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[4] 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\) は 臨時書き込み可能 である。

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

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

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

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

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.

出典

  1. Infinite Time Turing Machines
  2. http://arxiv.org/abs/math/9907044
  3. Bullets here indicate discarded portions of tuples.
  4. [1]
  5. http://www.maths.bris.ac.uk/~mapdw/pdw4.ps