ゼノン機械

ゼノン機械（ゼノンきかい、英: Zeno machine、ZM）は、数学および計算機科学においてチューリング機械と関係する仮説的な計算モデルで、可算無限個のアルゴリズム手順を有限の時間に実行することができる。加速チューリング機械（英: accelerated Turing machine、ATM）とも呼ばれる^[1]。こうした機械は殆どの（現実の原理的計算可能性を把握することを目的とした）計算モデルからは排除されている。

より正式には、ゼノン機械はチューリング機械であって第 n ステップの実行に 2⁻ⁿ 単位の時間が掛かるものである。それゆえ、最初のステップは 0.5 単位時間を要し、第二は 0.25、第三は 0.125、といった具合に、一単位時間の後に可算無限（つまり ℵ₀）個のステップが実行されるようになっている。

ゼノン機械の概念は1927年にヘルマン・ワイルによって初めて論じられた^[2]。それとは独立にR・M・ブレイク^[3] とバートランド・ラッセル^[4]によっても論じられている。その名前はゼノンのパラドックスを指しており、古代ギリシアの哲学者エレアのゼノンに由来する。ゼノン機械はいくつかの理論で重要な役割を果たす。例えば、物理学者フランク・ティプラーの考案したオメガ点（英語版）の理論は、ゼノン機械（の実現）が可能である場合に限って妥当である。

ゼノン機械と計算可能性

ゼノン機械はチューリング計算可能でないような或る関数の計算を可能にする。例えばチューリング機械の停止問題はゼノン機械によって解ける（以下の擬似コードアルゴリズムを用いる）^[5]。

  入力：チューリング機械  $T$ 、文字列  $w$ 
  出力テープの初期位置に  $0$  を印字する;
  begin loop
     $T(w)$  の計算を一段階だけシミュレートする
    もし  $T(w)$  の計算がこのステップで完了したなら、出力テープの初期位置に  $1$  を印字し、ループを抜ける
  end loop

このプログラムはゼノン機械によって一単位時間で実行される。計算が終了した時点で出力テープには停止問題の正しい解が印字される。

この種のチューリング限界の彼方にある計算はハイパーコンピュテーション（このケースのものはスーパータスクによるハイパーコンピュテーション）と呼ばれる。さらなる議論と文献については当該記事を参照。

参考文献

^ Copeland, B. Jack (2002). “Accelerating Turing Machines”. Minds and Machines 12: 281-301.
^ Weyl, Herman (1949) (English Translation). Philosophy of Mathematics and Natural Science. Princeton University Press
^ Blake, R. M. (1926). “The Paradox of Temporal Process”. The Journal of Philosophy 23 (24): 645-654.
^ Russell, Bertrand (1935-1936). “The Limits of Empiricism”. Proceedings of the Aristotelian Society 36: 31-150.
^ S. Calude, Cristian; Staiger, Ludwig (2010年). “A note on accelerated Turing machines”. Mathematical Structures in Computer Science 20 (6): pp. 1011-1017

ゼノン機械と計算可能性

参考文献

関連項目