تحسيب حقيقي
في نظرية الحسوبية، نظرية التحسيب الحقيقي تتعامل مع أجهزة حوسبة افتراضية تستخدم أعداد حقيقة غير محدودة الدقة.
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 and are differential, whereas digital computers are limited to computable numbers and are algebraic. 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).
A canonical model of computation over the reals is Blum–Shub–Smale machine (BSS).
Using real computation one can solve NP-complete problems, and even #P-complete problems in polynomial time, answering affirmatively the P = NP problem. Unlimited precision real numbers in the physical universe are prohibited by the holographic principle and the Bekenstein bound.
انظر أيضاً
- تحسيب فائق
مراجع
-
^ O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry (2007). "Polynomial differential equations compute all real computable functions on computable compact intervals". Journal of Complexity. 23 (3): 317–335. doi:10.1016/j.jco.2006.12.005. Unknown parameter
|month=ignored (help)CS1 maint: multiple names: authors list (link) - ^ Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.
قراءة إضافية
- Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale. Complexity and Real Computation. ISBN .CS1 maint: multiple names: authors list (link)
- Campagnolo, Manuel Lameiras (July 2001). 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. (PDF).CS1 maint: multiple names: authors list (link)
- Siegelmann, Hava. Neural Networks and Analog Computation: Beyond the Turing Limit. ISBN .
- Siegelmann, Hava & Sontag, Eduardo D. .CS1 maint: multiple names: authors list (link)]
