リアルコンピュエーション - 百科事典

計算可能性理論における実数計算理論は、無限精度の実数を使用する仮想的な計算機に関するものです。これらの計算機は実数の集合で操作することからこの名前が与えられます。この理論のなかで、「マandelbrot集合の補集合は部分決定可能だけ」といった興味深い主張を証明することができます。

これらの仮想的な計算機は、実数で動作する理想化されたアナログ計算機として見ることができ、一方でデジタル計算機は計算可能な数に限られています。さらに、これらは微分モデルおよび代数的モデル（この文脈ではデジタル計算機はトポロジカルなものと考えられますが、計算可能な実数に関する操作においては）にさらに分類できます。選択されたモデルによっては、実数計算機がデジタル計算機では解けない問題を解くことができたり、逆もありえます（例えば、Hava Siegelmannの神経網は計算不可能な実数の重みを持つことができ、非還元言語を計算することができます）。また、逆もありえます（Claude Shannonの理想化されたアナログ計算機は代数的微分方程式しか解けませんが、デジタル計算機は transcendental 方程式も解きます。ただし、この比較は完全には正しくありません。なぜなら、Claude Shannonの理想化されたアナログ計算機の計算は即座に行われるからです；つまり、計算はリアルタイムに行われます。Shannonのモデルはこの問題に対処するために適用することができます）。

実数に対する計算の典型モデルは、Blum–Shub–Smale機（BSS）です。

もし実数計算が物理的に実現可能であれば、それを使用してNP完問題や#P完問題を多項式時間で解くことができるでしょう。物理的な宇宙における無限精度の実数は、ホログラフィック原理とベッケンスタイン界によって禁止されています。

参考文献
* Hypercomputation、他の強力な機械について
* Real RAM
* Quantum finite automaton、任意の幾何学的空間への一般化

参考書籍
* Lenore Blum、Felipe Cucker、Michael Shub、Stephen Smale（1998）. Complexity and Real Computation. Springer. ISBN 0-387-98281-7.
* Campagnolo, Manuel Lameiras（2001年7月）. Computational complexity of real valued recursive functions and analog circuits. Universidade Técnica de Lisboa, Instituto Superior Técnico.
* Natschläger, Thomas、Wolfgang Maass、Henry Markram. The "Liquid Computer" A Novel Strategy for Real-Time Computing on Time Series（PDF）.
* Siegelmann, Hava（1998年12月）. Neural Networks and Analog Computation: Beyond the Turing Limit. Springer. ISBN 0-8176-3949-7.
* Siegelmann, Hava T.、Sontag, Eduardo D.（1995）. "On the computational power of neural nets"（PDF）. Journal of Computer and System Sciences. 50 (1): 132–150. doi:10.1006/jcss.1995.1013. MR 1322637.