Information AboutHypercomputer |
| CATEGORIES ABOUT HYPERCOMPUTATION | |
| theory of computation | |
|
HISTORY A model more powerful than Turing machines was introduced by Alan Turing in his 1939 paper ''Systems of logic based on ordinals''. This paper investigated mathematical systems in which an Oracle was available, which could compute a single arbitrary (non-recursive) function from Natural s to naturals. He used this device to prove that even in those more powerful systems, undecidability is present. Turing's writing made it clear that oracle machines were only mathematical abstractions, and were not thought of as physically realisable."Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper ''Systems of Logic Based On Ordinals'') THEORETICAL AND CONCEPTUAL POSSIBILITIES FOR A HYPERCOMPUTER
. Such a system could not be an ordinary Qubit Quantum Computer because it has been proved that regular quantum computers are Turing reducible (they may yield speedup for some problems, but they don't allow solving ''new'' problems). 4
As long as there is no physically plausible way to build such a device, hypercomputers will exist only as mathematical models. SEE ALSO NOTES Note: Kieu does not seem to have down graded his claim in his reply to Tsirelson's paper. He points out that Tsirelson's argument may be flawed or of limited applicability to his theorem. REFERENCES #Alan Turing, ''Systems of logic based on ordinals'', Proc. London math. soc., 45, 1939 #Hava Siegelman. ''Neural Networks and Analog Computation: Beyond the Turing Limit'' Boston: Birkhäuser. #Hava Siegelmann. ''The simple dynamics of super Turing theories'' ; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472. (link is to ScienceDirect website copy) #Keith Douglas. '' Super-Turing Computation: a Case Study Analysis '' ( PDF ), M.S. Thesis, Carnegie Mellon University, 2003. #L. Blum, F. Cucker, M. Shub, S. Smale, ''Complexity and Real Computation'', Springer-Verlag 1997. General development of complexity theory for Abstract Machine s that compute on real or Complex Number s instead of bits. # On the computational power of neural nets #Toby Ord. ''Hypercomputation: Computing more than the Turing machine can compute'' : A survey article on various forms of hypercomputation. |
|
|