ゼノン機械のソースを表示

'''ゼノン機械'''（ゼノンきかい、{{lang-en-short|Zeno machine}}、'''ZM'''）は、[[数学]]および[[計算機科学]]において[[チューリング機械]]と関係する仮説的な計算モデルで、[[可算無限]]個のアルゴリズム手順を有限の時間に実行することができる。'''加速チューリング機械'''（{{lang-en-short|accelerated Turing machine}}、'''ATM'''）とも呼ばれる<ref>{{Cite journal
| title = Accelerating Turing Machines
| last = Copeland
| first = B. Jack
| journal = Minds and Machines
| volume = 12
| year = 2002
| pages = 281-301
}}</ref>。こうした機械は殆どの（現実の原理的計算可能性を把握することを目的とした）計算モデルからは排除されている。

より正式には、ゼノン機械はチューリング機械であって第 ''n'' ステップの実行に 2<sup>−''n''</sup> 単位の時間が掛かるものである。それゆえ、最初のステップは 0.5 単位時間を要し、第二は 0.25、第三は 0.125、といった具合に、一単位時間の後に[[可算無限]]（つまり [[アレフ数#アレフ・ノート|&alefsym;<sub>0</sub>]]<!-- <math>\aleph_0</math> -->）個のステップが実行されるようになっている。

ゼノン機械の概念は1927年に[[ヘルマン・ワイル]]によって初めて論じられた<ref>{{Cite book
| title = Philosophy of Mathematics and Natural Science
| last = Weyl
| first = Herman
| publisher = Princeton University Press
| year = 1949
| language = English Translation
}}</ref>。それとは独立に[[R・M・ブレイク]]<ref>{{Cite journal
| title = The Paradox of Temporal Process
| last = Blake
| first = R. M.
| journal = The Journal of Philosophy
| volume = 23
| number = 24
| year = 1926
| pages = 645-654
}}</ref>
と[[バートランド・ラッセル]]<ref>{{Cite journal
| title = The Limits of Empiricism
| last = Russell
| first = Bertrand
| journal = Proceedings of the Aristotelian Society
| volume = 36
| year = 1935-1936
| pages = 31-150
}}</ref>によっても論じられている。その名前は[[ゼノンのパラドックス]]を指しており、古代ギリシアの哲学者[[エレアのゼノン]]に由来する。ゼノン機械はいくつかの理論で重要な役割を果たす。例えば、物理学者[[フランク・ティプラー]]の考案した{{仮リンク|オメガ点|en|Omega Point}}の理論は、ゼノン機械（の実現）が可能である場合に限って妥当である。

== ゼノン機械と計算可能性 ==

ゼノン機械はチューリング計算可能でないような或る関数の計算を可能にする。例えばチューリング機械の[[停止問題]]はゼノン機械によって解ける（以下の[[擬似コード]]アルゴリズムを用いる）<ref>{{Cite article
| title = A note on accelerated Turing machines
| first1 = Cristian
| last1 = S. Calude
| first2 = Ludwig
| last2 = Staiger
| journal = Mathematical Structures in Computer Science
| volume = 20
| number = 6
| year = 2010
| pages = 1011-1017
}}</ref>。

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

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

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

== 参考文献 ==
{{reflist}}

== 関連項目 ==
* [[ハイパーコンピュータ|ハイパーコンピュテーション]]
* {{仮リンク|ロス＝リトルウッドのパラドックス|en|Ross–Littlewood_paradox}}
* [[スーパータスク]]
* [[トムソンのランプ]]
* [[フランク・ティプラー#オメガ点|ティプラーのオメガ点]]
* [[ゼノンのパラドックス]]

{{デフォルトソート:せのんきかい}}
[[Category:計算モデル]]
[[Category:チューリングマシン]]
[[Category:ハイパーコンピュテーション]]
[[Category:スーパータスク]]
[[Category:数学に関する記事]]