ハイパーコンピューティング

ハイパーコンピューティングまたはスーパーチューリングコンピューティングは、チューリング計算不可能な出力を提供できる仮想的な計算モデルの集合です。たとえば、停止問題を解決できるマシンはハイパーコンピュータです。また、ペアノ算術のすべてのステートメントを正しく評価できるマシンもハイパーコンピュータです。

チャーチ＝チューリングのテーゼは、数学者がペンと紙を使って有限の単純なアルゴリズムを使って計算できる「計算可能な」関数は、チューリング マシンでも計算できると述べています。ハイパーコンピュータは、チューリング マシンでは計算できない関数を計算します。したがって、これはチャーチ＝チューリングの意味で計算可能ではありません。

技術的には、ランダム チューリング マシンの出力は計算不可能ですが、ほとんどのハイパーコンピューティングの文献では、ランダムな計算不可能な関数ではなく、決定論的な関数の計算に焦点を当てています。

チューリングマシンを超える計算モデルは、アラン・チューリングが1938年に発表した博士論文「順序数に基づく論理システム」で紹介された。^[1]この論文では、自然数から自然数への任意の（再帰的でない）関数を1つ計算できるオラクルが利用できる数学システムを調査した。彼はこの装置を使って、より強力なシステムでも決定不能性が存在することを証明した。チューリングのオラクルマシンは数学的な抽象概念であり、物理的に実現可能ではない。^[2]

ある意味では、ほとんどの関数は計算不可能である。計算可能な関数もあるが、超チューリング関数の可能な数は無数（ ）ある。 ^[3]${\displaystyle \aleph_{0}}$${\displaystyle 2^{\aleph _{0}}}$

ハイパーコンピュータ モデルは、有用だがおそらく実現不可能なもの (チューリングのオリジナルのオラクル マシンなど) から、有用性は低いがおそらく「実現可能」なランダム関数ジェネレータ (ランダム チューリング マシンなど) まで多岐にわたります。

計算不可能な、予言的なチャイティン定数(停止問題の解をエンコードする無限の数字列を持つ数) の知識を入力として与えられたシステムは、多数の有用な決定不可能な問題を解決できます。計算不可能な乱数ジェネレータを入力として与えられたシステムは、ランダムな計算不可能な関数を作成できますが、停止問題などの「有用な」計算不可能な関数を意味のある形で解決できるとは一般に考えられていません。考えられるハイパーコンピュータには、以下を含む無数の異なるタイプがあります。

• チューリングが 1939 年に定義したチューリングのオリジナルのオラクル マシン。
• 実際のコンピュータ（一種の理想化されたアナログコンピュータ）は^、物理学が一般的な実変数（計算可能な実数だけでなく）を認め、これらが何らかの方法で（ランダムではなく）有用な計算に「利用できる」場合、ハイパーコンピューティング [4] を実行できます。これには、かなり奇妙な物理法則（たとえば、チャイティン定数などの神託値を持つ測定可能な物理定数）が必要になる可能性があり、実数値の物理値を任意の精度で測定する機能が必要になりますが、標準的な物理学では、そのような任意の精度の測定は理論的に実行不可能です。^[5]
  • 同様に、チャイティン定数を重み関数に正確に組み込まれたニューラルネットは停止問題を解決できるが^[6]、実際の計算に基づく他のハイパーコンピューティングモデルと同じ物理的な困難に悩まされる。
• 特定のファジー論理ベースの「ファジーチューリングマシン」は、定義上、停止問題を偶然に解決することができるが、それは停止問題を解決できる能力がマシンの仕様で間接的に想定されているためであり、これはマシンの元の仕様における「バグ」と見なされる傾向がある。^{[7] [8]}
  • 同様に、公正な非決定性として知られる提案モデルは、計算不可能な関数の予言的計算を偶然に許可する可能性があります。なぜなら、そのようなシステムの中には、定義上、サブシステムを永久に実行させる「不公平な」拒否入力を識別する予言的能力を持つものがあるからです。^{[9] [10]}
• ドミトロ・タラノフスキーは、伝統的に非有限的であった解析分野の有限モデルを提案した。これは、急速に増加する関数をオラクルとして備えたチューリングマシンを中心に構築されたものである。このモデルとより複雑なモデルによって、彼は2階算術の解釈を与えることができた。これらのモデルは、イベント間の間隔が計算不可能なほど大きな速度で増加する物理的なイベント生成プロセスなど、計算不可能な入力を必要とする。^[11]
  • 同様に、無制限の非決定性モデルの非正統的な解釈の1つは、定義により、「アクター」が落ち着くのに必要な時間の長さは基本的に知ることができないため、モデル内では計算できないほど長い時間がかからないことを証明することはできないと仮定している。^[12]

正しく動作するために、以下のマシンによる特定の計算には、文字通り、無制限ではなく有限の物理空間とリソースが必要です。対照的に、チューリング マシンでは、停止する任意の計算には有限の物理空間とリソースのみが必要です。

有限の時間内に無限のステップを完了できるチューリングマシン。これはスーパータスクと呼ばれる。単に無限の数のステップを実行できるだけでは十分ではない。1つの数学モデルはゼノマシン（ゼノのパラドックスに触発された）である。ゼノマシンは最初の計算ステップを（たとえば）1分で実行し、2番目のステップを0.5分で、3番目のステップを1/4分で実行する。1 + 1/2 + 1/4 + ...（等比級数）を合計すると、マシンが合計2分で無限のステップを実行することがわかる。オロン・シャグリアによると、ゼノマシンは物理的なパラドックスを導入し、その状態は[0, 2)の片側開期間外では論理的に未定義であるため、計算開始からちょうど2分後に未定義になる。^[13]

タイムトラベルの可能性（閉じた時間的曲線（CTC）の存在）がそれ自体でハイパーコンピューティングを可能にするのは当然のように思えます。しかし、CTCは（それ自体では）無限の計算に必要な無制限の量のストレージを提供しないため、そうではありません。それでも、CTC領域を相対論的ハイパーコンピューティングに使用できる時空があります。^[14] 1992年の論文によると、^[15]マラメント-ホガース時空または回転するブラックホールの周りの軌道で動作するコンピューターは^、理論的にはブラックホール内の観測者に対して非チューリング計算を実行できます。^{[17] [18]} CTCへのアクセスにより、チューリング決定可能ではあるものの、一般的に計算上は手に負えないと考えられている複雑性クラスであるPSPACE完全な問題を迅速に解決できる可能性があります。 ^{[19] [20]}

一部の学者は、何らかの形で状態の無限の重ね合わせを使用する量子力学システムは、計算不可能な関数を計算できると推測しています。^{[21]これは、標準的な}量子ビットモデルの量子コンピュータでは不可能です。なぜなら、通常の量子コンピュータはPSPACE縮小可能であることが証明されているからです（多項式時間で動作する量子コンピュータは、多項式空間で動作する古典コンピュータによってシミュレートできます）。^[22]

物理的に実現可能なシステムの中には、最終的には必ず正しい答えに収束するものもあるが、間違った答えを出力し、最終的に戻って間違いを修正するまで、計算不可能なほど長い時間その間違った答えに固執することが多いという欠陥がある。

1960 年代半ば、E マーク ゴールドとヒラリー パトナムはそれぞれ独立して帰納的推論のモデル(「極限再帰関数」^[23]と「試行錯誤述語」^[24] ) を提案しました。これらのモデルにより、非再帰的な数や言語の集合 (再帰的に列挙可能なすべての言語の集合を含む) を「極限で学習」できるようになりました。一方、定義により、チューリング マシンで識別できるのは再帰的な数や言語の集合のみです。マシンは、学習可能な集合に対して有限時間内に正しい答えに安定しますが、正しいと識別できるのは、それが再帰的である場合のみです。そうでない場合、マシンを永久に実行し、答えを修正しないことに気付くことによってのみ、正しさが確立されます。パトナムは、この新しい解釈を「経験的」述語のクラスと見なし、「常に最も最近生成された答えが正しいと仮定すると、有限数の間違いを犯すことになりますが、最終的には正しい答えが得られます。（ただし、正しい答え（有限シーケンスの終わり）に到達したとしても、正しい答えを得たかどうかは決して確信できないことに注意してください。）」と述べています。 ^[24] LK シューベルトの 1974 年の論文「反復極限再帰とプログラム最小化問題」^[25]は、極限手順の反復の効果を研究しました。これにより、任意の算術述語を計算できます。シューベルトは、「直感的に、反復極限識別は、ますます増え続ける低次の帰納的推論マシンのコミュニティによって集合的に実行される高次の帰納的推論と見なすことができます」と書いています。

記号列が極限で計算可能であるのは、その記号列のすべての記号を増分的に出力する、有限でおそらく非停止のプログラムが汎用チューリングマシン上に存在する場合である。これには、π の二項展開と他のすべての計算可能な実数の二項展開が含まれるが、計算不可能な実数はすべて除外される。記述サイズ理論で伝統的に使用されている「単調チューリングマシン」は、以前の出力を編集できないが、ユルゲン・シュミットフーバーによって定義された一般化チューリングマシンは編集できる。彼は、構成的に記述可能な記号列を、一般化チューリングマシン上で実行される有限で非停止のプログラムを持ち、出力記号が最終的に収束する、つまり、有限の初期時間間隔の後にそれ以上変化しないものとして定義している。Kurt Gödel (1931) によって初めて示された制限により、停止プログラムによって収束時間自体を予測することは不可能である可能性があるが、そうでなければ停止問題を解決できる可能性がある。シュミットフーバー（^{[26] [27]}）はこのアプローチを使用して、形式的に記述可能または構成的に計算可能な宇宙、または万物の構成理論の集合を定義します。一般化されたチューリングマシンは、スペッカーシーケンスを評価することで、最終的に停止問題の正しい解に収束することができます。

多くのハイパーコンピューティングの提案は、古典的なマシンに埋め込まれたオラクルやアドバイス関数を読み取るための代替方法に相当します。他の提案は、算術階層のより高いレベルへのアクセスを許可します。たとえば、スーパータスク チューリング マシンは、通常の仮定の下では、またはを含む真理値表次数の任意の述語を計算できます。対照的に、制限再帰は、対応するチューリング次数（であることが知られています）の任意の述語または関数を計算できます。ゴールドはさらに、制限部分再帰によって述語を正確に計算できることを示しました。 ${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Delta _{2}^{0}}$${\displaystyle \Sigma _{2}^{0}}$

マーティン・デイビスは、ハイパーコンピューティングに関する著書^{[34] [35]}の中で、 この主題を「神話」と呼び、ハイパーコンピューティングの物理的実現可能性に対する反論を行っている。理論に関しては、これは1990年代に設立された新しい分野であるという主張に反論している。この見解は、上でも述べたように、計算可能性理論（解けない程度、関数、実数、順序数上の計算可能性）の歴史に依存している。彼の議論では、ハイパーコンピューティングのすべては「計算不可能な入力が許されるなら、計算不可能な出力も達成可能」に過ぎないと述べている。 [ 36 ^]

• デジタル物理学
• 計算の限界

• Aoun, Mario Antoine (2016). 「3つのハイパーコンピューティングモデルの進歩」(PDF) . Electronic Journal of Theoretical Physics . 13 (36): 169–182. 2017-02-06 にオリジナル(PDF)からアーカイブ。2023-07-28に取得。
• Burgin, MS (1983). 「帰納的チューリングマシン」.ソ連科学アカデミーの通知. 270 (6): 1289–1293.
• Burgin, Mark (2005)。超再帰アルゴリズム。コンピュータサイエンスのモノグラフ。Springer。ISBN 0-387-95569-0。
• Cockshott, P.; Michaelson , G. (2007)。「新しい計算モデルはあるか? Wegner と Eberbach への返答」。The Computer Journal。doi : 10.1093/comjnl/bxl062。
• Cooper, SB; Odifreddi, P. (2003). 「自然界における計算不可能性」(PDF)。Cooper, SB; Goncharov, SS (編)。計算可能性とモデル: 東西の視点。ニューヨーク、ボストン、ドルドレヒト、ロンドン、モスクワ: Plenum Publishers。pp. 137–160。2011-07-24 にオリジナル(PDF)からアーカイブ。2011-06-16に取得。
• Cooper, SB (2006). 「ハイパー計算効果としての定義可能性」.応用数学と計算. 178 : 72–82. CiteSeerX  10.1.1.65.4088 . doi :10.1016/j.amc.2005.09.072. S2CID  1487739.
• Copeland, J. (2002). 「ハイパーコンピューティング」(PDF) . Minds and Machines . 12 (4): 461–502. doi :10.1023/A:1021105915386. S2CID 218585685. 2016-03-14 に オリジナル(PDF)からアーカイブ。
• Hagar, A.; Korolev, A. (2007). 「量子ハイパーコンピューティング - 誇大広告か計算か?*」(PDF) .科学哲学. 74 (3): 347–363. doi :10.1086/521969. S2CID  9857468.
• Ord, Toby (2002)。 「ハイパーコンピューティング: チューリングマシンの計算能力を超える計算: さまざまな形式のハイパーコンピューティングに関する調査記事」。arXiv : math/0209332。
• ピチニーニ、グアルティエロ（2021年6月16日）。「物理システムにおける計算」スタンフォード哲学百科事典。 2023年7月31日閲覧。
• Sharma, Ashish (2022). 「ランダム化されたハイパーコンピューティングの観点から見た自然にインスパイアされたアルゴリズム」.情報科学. 608 : 670–695. doi :10.1016/j.ins.2022.05.020. S2CID  248881264.
• スタンネット、マイク (1990)。「X マシンと停止問題: スーパーチューリングマシンの構築」。コンピューティングの形式的側面。2 (1): 331–341。doi : 10.1007/ BF01888233。S2CID  7406983 。
• スタンネット、マイク (2006)。「ハイパーコンピューティングのケース」(PDF)。応用数学と計算。178 (1): 8–24。doi : 10.1016 / j.amc.2005.09.067。2016-03-04にオリジナル(PDF)からアーカイブ。
• シロポロス、アポストロス (2008)。ハイパーコンピューティング：教会とチューリングの壁を越えたコンピューティング。シュプリンガー。ISBN 978-0-387-30886-9。