ハイパーコンピュータ

ハイパーコンピュータ︵英: Hypercomputer︶は、非計算可能関数を計算できる仮想的なコンピュータである。ハイパーコンピュータを使った計算を Hypercomputation という。Jack Copeland が生み出した造語である。類似の用語として﹁超チューリング計算︵super-Turing computation︶﹂があるが、ハイパーコンピュータと言った場合には、そのようなコンピュータが物理的に構築可能かもしれないという意味も若干含まれていることがある。実数で重み付けするニューラルネットワーク、無限に多数の計算を同時並行して実施可能なモデル、チューリング機械で計算できないものを計算可能なモデル、などのいくつかのモデルが提案されており、一般に実数値の連続関数の極限や積分を︵近似ではなく︶全く誤差なく計算できるとされる。

歴史

チューリング機械よりも強力なモデルは、1939年のアラン・チューリングの論文 Systems of logic based on ordinals に登場した。この論文は、自然数から自然数への任意の︵再帰的でない︶所与の関数を計算できる神託機械を持つ数学的システムを研究したものであった。︵神託機械も参照のこと。︶彼はこのような機械を想定することで、このようなより強力なシステムであっても、依然として決定不可能性が存在することを証明した。チューリングは、神託機械を数学的抽象のために導入したのであって、それが物理的に実現可能とは思っていなかった。

ハイパーコンピュータの提案

●無限に多数のステップを実行完了できるチューリング機械。単に、無限の計算量を実行可能なだけでは不十分である。前提として、有限の時間内に全ての計算を終了させる必要がある。提案されている例としては、時間の遅れを利用して、ハイパーコンピュータが無限の時間を使って計算している間に観測者は有限の時間経過しか観測しない、という方式がある︵この場合、計算には無限大のエネルギーを要する︶。別の例として、ゼノンのパラドックスから着想された純粋な数学的モデルであるゼノン機械︵Zeno machine︶がある。ゼノン機械では、最初の1ステップを︵例えば︶1分で行い、次のステップを0.5分で行い、さらに次のステップを0.25分で行う、というように1ステップにかかる時間が半減していく。この時間を無限ステップまで合計すると、2分で無限ステップを実行できることになる。

●無限時間チューリング機械は、ゼノン機械を一般化したもので、潜在的に超限的な順序数によって列挙されるステップ数を要する無限に長い計算を実行できる。このチューリング機械は、停止しない計算において極限順序数に達したときに特別な状態に遷移して完了し、そこまでの無限の計算の結果が利用可能という点以外は普通のチューリング機械である。

●実数コンピュータ︵理想のアナログコンピュータ︶を Hypercomputation に使うこともある。これには物理定数︵例えばチャイティンの定数︶を無限の精度で与えるといった考慮が必要と考えられ、少なくとも熱雑音や量子効果があったとしても任意の精度で実数の物理的値を測定できる必要がある。

●量子力学系の状態の無限な重ね合わせを使って、非計算可能関数を計算する。ただし、標準的な量子ビットを使った量子コンピュータはチューリング還元可能︵計算を高速化できても、これまで解けなかった問題は解けない︶と一般に予想されているため、ハイパーコンピュータとしては使えないと考えられている。

●無制限の非決定性と呼ばれる技法を使って非計算可能関数を計算できるのではないかとも言われている。ただし、その無矛盾性や計算能力には疑問も投げかけられている。

今のところ、ハイパーコンピュータを実際に作ることは不可能とされており、概念が提示されるのみに留まっている。

関連項目

• チャーチ＝チューリングのテーゼ
• 神託機械

参考文献

• 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

外部リンク

• Hypercomputation Research Network
• Toby Ord, Hypercomputation: computing more than the Turing machine
• Toby Ord, The many forms of hypercomputation
• Paolo Cotogno, Hypercomputation and the Physical Church-Turing thesis