ハイパーコンピュータ
提供: miniwiki
ハイパーコンピュータ（英: Hypercomputer）は、非計算可能関数を計算できる仮想的なコンピュータである。ハイパーコンピュータを使った計算を Hypercomputation という。Jack Copeland が生み出した造語である。類似の用語として「超チューリング計算（super-Turing computation）」があるが、ハイパーコンピュータと言った場合には、そのようなコンピュータが物理的に構築可能かもしれないという意味も若干含まれていることがある。実数で重み付けするニューラルネットワーク、無限に多数の計算を同時並行して実施可能なモデル、チューリング機械で計算できないものを計算可能なモデル、などのいくつかのモデルが提案されており、一般に実数値の連続関数の極限や積分を（近似ではなく）全く誤差なく計算できるとされる。
歴史
チューリング機械よりも強力なモデルは、1939年のアラン・チューリングの論文 Systems of logic based on ordinals に登場した。この論文は、自然数から自然数への任意の（再帰でない）関数を計算できる神託機械を持つ数学的システムを研究したものであった。彼はこのような機械を想定することで、より強力な機械があったとしても依然として非決定性が存在することを証明した。チューリングは、神託機械を数学的抽象のために導入したのであって、それが物理的に実現可能とは思っていなかった[1]。
ハイパーコンピュータの提案
- 無限に多数のステップを実行完了できるチューリング機械。単に、無限の計算量を実行可能なだけでは不十分である。前提として、有限の時間内に全ての計算を終了させる必要がある。提案されている例としては、時間の遅れを利用して、ハイパーコンピュータが無限の時間を使って計算している間に観測者は有限の時間経過しか観測しない、という方式がある（この場合、計算には無限大のエネルギーを要する）。別の例として、ゼノンのパラドックスから着想された純粋な数学的モデルであるゼノマシン（Zeno machine）がある。ゼノマシンでは、最初の1ステップを（例えば）1分で行い、次のステップを0.5分で行い、さらに次のステップを0.25分で行う、というように1ステップにかかる時間が半減していく。この時間を無限ステップまで合計すると、2分で無限ステップを実行できることになる。
- 無限時間チューリング機械は、ゼノマシンを一般化したもので、潜在的に超限的な順序数によって列挙されるステップ数を要する無限に長い計算を実行できる。このチューリング機械は、停止しない計算において極限順序数に達したときに特別な状態に遷移して完了し、そこまでの無限の計算の結果が利用可能という点以外は普通のチューリング機械である[2]。
- 実数コンピュータ（理想のアナログコンピュータ）を Hypercomputation に使うこともある[3]。これには物理定数（例えばチャイティンの定数）を無限の精度で与えるといった考慮が必要と考えられ、少なくとも熱雑音や量子効果があったとしても任意の精度で実数の物理的値を測定できる必要がある。
- 量子力学系の状態の無限な重ね合わせを使って、非計算可能関数を計算する[4]。ただし、標準的な量子ビットを使った量子コンピュータはチューリング還元可能（計算を高速化できても、これまで解けなかった問題は解けない）と一般に予想されているため、ハイパーコンピュータとしては使えないと考えられている[5]。
- 無制限の非決定性と呼ばれる技法を使って非計算可能関数を計算できるのではないかとも言われている。ただし、その無矛盾性や計算能力には疑問も投げかけられている。
今のところ、このような計算機を実際に作ることは不可能とされており、ハイパーコンピュータは数学上の概念としてのみ存在している。
脚注
- ↑ "Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper Systems of Logic Based On Ordinals)
- ↑ Joel David Hamkins and Andy Lewis, Infinite time Turing machines, Journal of Symbolic Logic, 65(2):567-604, 2000.“アーカイブされたコピー”. 2011年10月5日時点のオリジナルよりアーカイブ。. 2008年1月15日閲覧.
- ↑ Arnold Schönhage, "On the power of random access machines", in Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 520-529, 1979. Source of citation: Scott Aaronson, "NP-complete Problems and Physical Reality"[1] p. 12
- ↑ このような主張がいくつかある。例えば Tien Kieu (2003年). “Quantum Algorithm for the Hilbert's Tenth Problem”. Int. J. Theor. Phys. 42: 1461-1478. など。Warren D. Smith は Three counterexamples refuting Kieu’s plan for “quantum adiabatic hypercomputation”; and some uncomputable quantum mechanical tasks の中で Kieu の間違いを指摘している。
- ↑ Michael Nielsen and Isaac Chuang (2000年). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
関連項目
参考文献
- Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
- Hava Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
- Hava Siegelmann. The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472. (link is to ScienceDirect website copy)
- Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
- L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. ビットではなく実数を計算する抽象機械についての計算複雑性理論
- On the computational power of neural nets
- Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: Hypercomputation の各種形態についての調査
- Apostolos Syropoulos, Hypercomputation: Computing Beyond the Church-Turing Barrier, 2008