ai architecture article complexity computability-theory computation-theory computer computerscience computing cs fun hypercomputation importedfurl20071006 incompleteness interactivecomputation jhu logic physics programación quantum quantumcomputing relativity science science-fiction turing

My tags:

From Wikipedia, the free encyclopedia

Hypercomputation refers to various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms (see also supertask). The term was first introduced in 1999 by Jack Copeland and Diane Proudfoot^[1]. A similar term is super-Turing computation, was previously introduced and demonstrated by Hava Siegelmann. Hypercomputation may have the additional connotation of entertaining the possibility that such a device could be physically realizable. Some models have been proposed, already by Siegelmann, such as neural networks with real numbers as weights, the ability to carry out infinitely many computations simultaneously, or the ability to perform non-Turing computable operations, such as limits or integrations on general (i.e. not just trivial) real-valued continuous functions that are exact rather than approximate.

Contents 1 History 2 Hypercomputer proposals 3 See also 4 Bibliography 5 References 6 External links

[edit] 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 naturals to naturals. He used this device to prove that even in those more powerful systems, undecidability is still present. Turing's writing made it clear that oracle machines were only mathematical abstractions, and were not thought of as physically realisable.^[2]

[edit] Hypercomputer proposals

• A Turing machine that can complete infinitely many steps. Simply being able to run for an unbounded number of steps forever, (i.e. potential infinity) does not suffice. One proposed example uses time dilation to allow a computer to spend an infinite amount of time performing a computation while a finite amount of time passes for an observer (it would require an infinite amount of energy to perform this calculation--see Malament-Hogarth spacetime). Another example is the Zeno machine (inspired by Zeno's paradox), a purely mathematical model. The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc. By summing the infinite geometric series 1+½+¼+... we see that the machine performs infinitely many steps in a total of 2 minutes. However, some people claim that, following the reasoning from Zeno's paradox, Zeno machines are not just physically impossible, but logically impossible.^[3]
• The infinite time Turing machine is a generalization of the Zeno machine, that can perform infinitely long computations whose steps are enumerated by potentially transfinite ordinal numbers. It models an otherwise-ordinary Turing machine for which non-halting computations are completed by entering a special state reserved for reaching a limit ordinal and to which the results of the preceding infinite computation are available.^[4]
• A real computer (a sort of idealized analog computer) might be able to perform hypercomputation ^[5] if physics admits general real variables (not just computable reals), and these are in some way "harnessable" for computation. This might require quite bizarre laws of physics (for example, a measurable physical constant with an oracular value, such as Chaitin's constant), and would at minimum require the ability to measure a real-valued physical value to arbitrary precision despite thermal noise and quantum effects.
• A quantum mechanical system which somehow uses (for example) an infinite superposition of states to compute a non-computable function.^[6] This is not possible using the standard qubit-model quantum computer, because it is proven that a regular quantum computer is PSPACE-reducible (a quantum computer running in polynomial time can be simulated by a classical computer running in polynomial space). ^[7]
• A technique known as fair nondeterminism or unbounded nondeterminism may allow the computation of noncomputable functions. There is dispute in the literature over whether this technique is coherent, and whether it actually allows noncomputable functions to be "computed".
• The use of closed timelike curves (CTC), contrary to the beliefs of some, do not appear to permit hypercomputation, since they do not provide the unbounded amount of storage that an infinite computation would require. However, access to a CTC may allow the rapid solution to PSPACE-complete problems, a complexity class which while Turing-decidable is generally considered computationally intractable.^[8][9]
• In the early 1990s, Hava Siegelmann proposed a new computational model, the Artificial Recurrent Neural Network (ARNN), and proved that it could perform hypercomputation. It is based on evolving an artificial neural network through an infinite succession of states.^[10].

[edit] See also

• Church-Turing thesis
• Oracle machine
• Zeno machine
• Computation
• Supertask
• Zeno paradox

[edit] Bibliography

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.^{[citation needed]}

[edit] References

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. Hava Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
3. Hava Siegelmann. The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472.
4. Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
5. L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
6. On the computational power of neural nets
7. Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
8. Apostolos Syropoulos (2008), Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer. ISBN 9780387308869
9. Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289-1293
10. Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690
11. Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
12. Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461-502
13. Martin Davis (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
14. Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation – Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
15. Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

[edit] External links

• Hypercomputation Research Network
• Toby Ord, Hypercomputation: computing more than the Turing machine
• Toby Ord, The many forms of hypercomputation
• Paolo Cotogno, Hypercomputation and the Physical Church-Turing thesis