| 词条 | Real computation |
| 释义 |
In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of real numbers. Within this theory, it is possible to prove interesting statements such as "The complement of the Mandelbrot set is only partially decidable." These hypothetical computing machines can be viewed as idealised analog computers which operate on real numbers, whereas digital computers are limited to computable numbers. They may be further subdivided into differential and algebraic models (digital computers, in this context, should be thought of as topological, at least insofar as their operation on computable reals is concerned[1]). Depending on the model chosen, this may enable real computers to solve problems that are inextricable on digital computers (For example, Hava Siegelmann's neural nets can have noncomputable real weights, making them able to compute nonrecursive languages.) or vice versa. (Claude Shannon's idealized analog computer can only solve algebraic differential equations, while a digital computer can solve some transcendental equations as well. However this comparison is not entirely fair since in Claude Shannon's idealized analog computer computations are immediately done; i.e. computation is done in real time. Shannon's model can be adapted to cope with this problem.)[2] A canonical model of computation over the reals is Blum–Shub–Smale machine (BSS). If real computation were physically realizable, one could use it to solve NP-complete problems, and even #P-complete problems, in polynomial time. Unlimited precision real numbers in the physical universe are prohibited by the holographic principle and the Bekenstein bound.[3] See also
References1. ^{{cite book|title=A Simple Introduction to Computable Analysis|author=Klaus Weihrauch|year=1995|url=http://eccc.uni-trier.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/}} 2. ^{{cite journal|author1=O. Bournez |author2=M. L. Campagnolo |author3=D. S. Graça |author4=E. Hainry |last-author-amp=yes |title=Polynomial differential equations compute all real computable functions on computable compact intervals|journal=Journal of Complexity|volume=23|issue=3|pages=317–335|date=Jun 2007|doi=10.1016/j.jco.2006.12.005}} 3. ^Scott Aaronson, [https://arxiv.org/abs/quant-ph/0502072 NP-complete Problems and Physical Reality], ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52. Further reading
2 : Theory of computation|Hypercomputation |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。