実際の計算

計算可能性理論では、実計算の理論は、無限精度の実数を使用する仮想計算機を扱います。これらは実数の集合に対して演算を行うため、この名前が付けられています。この理論では、「マンデルブロ集合の補集合は部分的にしか決定できない」などの興味深い主張を証明することができます。

これらの仮想計算機は、実数で動作する理想化されたアナログ計算機と見なすことができます。一方、デジタル計算機は計算可能な数に限定されています。これらはさらに、微分モデルと代数モデルに分類できます (この文脈では、デジタル計算機は、少なくとも計算可能な実数での動作に関する限り、位相的であると考える必要があります^[1] )。選択したモデルによっては、デジタル計算機では解決できない問題を実際の計算機で解決できる場合があります (たとえば、Hava Siegelmannのニューラル ネットは計算不可能な実数の重みを持つことができるため、非再帰言語を計算できます)。またはその逆も可能です。 （クロード・シャノンの理想化されたアナログコンピュータは代数微分方程式しか解けないが、デジタルコンピュータは超越方程式も解くことができる。しかし、この比較は完全に公平ではない。なぜなら、クロード・シャノンの理想化されたアナログコンピュータでは計算が即座に行われる、つまりリアルタイムで行われるからである。シャノンのモデルはこの問題に対処するために適応できる。）^[2]

実数上の計算の標準的なモデルは、Blum-Shub-Smale マシン(BSS) です。

もし実際の計算が物理的に実現可能であれば、NP完全問題、さらには#P完全問題さえも多項式時間で解くことができるだろう。物理宇宙における無制限の精度の実数は、ホロ​​グラフィック原理とベッケンシュタインの限界によって禁じられている。^[3]

• 他の強力なマシン向けのハイパーコンピューティング。
• 実際のRAM。
• 任意の幾何学的空間への一般化のための量子有限オートマトン。

• Lenore Blum 、Felipe Cucker 、 Michael Shub、Stephen Smale (1998)。複雑性と実計算。Springer。ISBN 0-387-98281-7。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
• カンパニョーロ、マヌエル・ラメイラス (2001 年 7 月)。実数値の再帰関数とアナログ回路の計算の複雑さ。リスボア技術大学、高等技術研究所。
• ナチュレーガー、トーマス、ヴォルフガング・マース、ヘンリー・マークラム。 「液体コンピューター」時系列でのリアルタイム コンピューティングの新しい戦略(PDF)。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
• シーゲルマン、ハヴァ（1998年12月）。ニューラルネットワークとアナログ計算：チューリング限界を超えて。シュプリンガー。ISBN 0-8176-3949-7。
• Siegelmann, Hava T. ; Sontag, Eduardo D. (1995). 「ニューラル ネットの計算能力について」(PDF) . Journal of Computer and System Sciences . 50 (1): 132–150. doi :10.1006/jcss.1995.1013. MR  1322637.