FANDOM


無限時間チューリングマシン (ITTMs) はチューリングマシンの順序数に対する一般化である。

定義 編集

元々のチューリングマシンの特性に加えて、ITTMsは極限状態(開始状態や終了状態に似ている)という特別な状態を持っている。 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 the 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 initial cell 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 tape 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 tape at \(t = \beta\) for all \(\beta < \alpha\).

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 trivial input can write \(\alpha\) and immediately halt.
  • An ordinal \(\alpha\) is clockable iff an ITTM with trivial input halts at time \(\alpha\).
  • An ordinal \(\alpha\) is eventually writable iff the output tape of an ITTM with trivial input ultimately converges to \(\alpha\).
  • An ordinal \(\alpha\) is accidentally writable iff an ITTM with trivial input writes \(\alpha\) at any step.

(The first three 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\)[1].

Fundamental sequences 編集

Fundamental sequences for these ordinals are reasonably simple to define, allowing use in FGH:

  • \(\lambda[n]\) is the supremum of all ordinals writable with ITTMs with at most \(n\) states. The function \(f(n) = \lambda[n]\) is in direct analogy with the busy beaver function.
  • \(\gamma[n]\) is the supremum of all ordinals clockable with ITTMs with at most \(n\) states.
  • \(\zeta[n]\) is the supremum of all ordinals eventually writable with ITTMs with at most \(n\) states.

It may seem that "the supremum of all ordinals accidentally writable with ITTMs with at most \(n\) states" would produce a fundamental sequence for \(\Sigma\). However, there exist "universal" ITTMs capable of accidentally writing all accidentally writable ordinals, so this definition has \(\Sigma[N] = \Sigma\) for some finite \(N\), which is clearly wrong.

Encoding ordinals in bitstrings 編集

Here is a simple way to encode an ordinal in a countably infinite bitstring (read: output tape of a two-color ITTM):

  • "1000..." encodes \(0\).
  • If string S encodes \(\alpha\), then the string "0" + S encodes \(\alpha + 1\).
  • If strings \(S_0,S_1,S_2,\ldots\) encode \(\alpha_0,\alpha_1,\alpha_2,\ldots\), let \(T\) be the string "0010120123012340123450123456...". Replace the instances of "0" in \(T\) with successive characters of \(S_0\), replace the instances of "1" with successive characters of \(S_1\), and so forth, producing \(T'\). The string "1" + \(T'\), then, encodes \(\sup\{\alpha_i\}\).

Note that the sequence "001012012301234..." is sufficient but not necessary. Any sequence consisting of infinite copies of every nonnegative integer will work. A computationally simpler alternative (albeit harder to understand) uses the fingerprint "0102010301020104010201030102010...", the ruler sequence.

編集

単テープマシン編集

\(\gamma[1] = \omega^2\)

\(\gamma[2] ≥ \omega^3\)

\(\gamma[3] ≥ \omega^4\)

\(\gamma[4] ≥ \omega^5\)

...

\(\gamma[7] ≥ \omega^\omega\)

\(\gamma[22] ≥ \omega^{\omega2}\)

最高出力マシン編集

\(\gamma[1] ≥ \omega^4\)

\(\gamma[4] ≥ \omega^\omega\)

出典編集

  1. http://www.maths.bris.ac.uk/~mapdw/pdw4.ps

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki