Super-recursive algorithm
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (February 2023) |
In computability theory, super-recursive algorithms are a generalization of hypercomputation: hypothetical algorithms that are more powerful, that is, compute more than Turing machines[citation needed].
The term was introduced by Mark Burgin, whose book Super-recursive algorithms develops their theory and presents several mathematical models.
Burgin argues that super-recursive algorithms can be used to disprove the Church-Turing thesis. This point of view has been criticized within the mathematical community and is not widely accepted.
Definition
Burgin (2005: 13) uses the term recursive algorithms for algorithms that can be implemented on Turing machines, and uses the word algorithm in a more general sense. Then a super-recursive class of algorithms is "a class of algorithms in which it is possible to compute functions not computable by any Turing machine" (Burgin 2005: 107)
Super-recursive algorithms are also related to algorithmic schemes, which are more general than super-recursive algorithms. Burgin argues (2005: 115) that it is necessary to make a clear distinction between super-recursive algorithms and those algorithmic schemes that are not algorithms. Under this distinction, some types of hypercomputation are obtained by super-recursive algorithms, e.g., inductive Turing machines, wile other types of hypercomputation are directed by algorithmic schemas, e.g., infinite time Turing machines. This explains how works on super-recursive algorithms are related to hypercomputation and vice versa. According to this argument, super-recursive algorithms are just one way of defining a hypercomputational process.
Relation to the Church–Turing thesis
The Church–Turing thesis in recursion theory relies on a particular definition of the term algorithm. Based on definitions that are more general than the one commonly used in recursion theory, Burgin argues that super-recursive algorithms, such as inductive Turing machines disprove the Church–Turing thesis. He furthermore claims to prove that super-recursive algorithms could hypothetically provide even greater efficiency gains than using quantum algorithms.
Burgin's interpretation of super-recursive algorithms has encountered opposition in the mathematical community. One critic is logician Martin Davis, who argues that Burgin's claims have been well understood "for decades". Davis states,
- "The present criticism is not about the mathematical discussion of these matters but only about the misleading claims regarding physical systems of the present and future."(Davis 2006: 128)
Davis disputes Burgin's claims that sets at level of the arithmetical hierarchy can be called computable, saying
- "It is generally understood that for a computational result to be useful one must be able to at least recognize that it is indeed the result sought." (Davis 2006: 128)
References
- Burgin, Mark (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
- José Félix Costa, MR2246430 Review in MathSciNet.
- Harvey Cohn (2005), CR131542 (0606-0574) Review in Computing Reviews
- Martin Davis (2007),Review in Bulletin of Symbolic Logic, v. 13 n. 2.
- Marc L. Smith (2006), Review in The Computer Journal, Vol. 49 No. 6
- Review, Vilmar Trevisan (2005), Zentralblatt MATH, Vol. 1070. Review 1070.68038
- Davis, Martin (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
- Hagar, A. and Korolev, A. (2007) "Quantum Hypercomputation – Hype or Computation?"
- Peter Kugel, "It's time to think outside the computational box", Communications of the ACM, Volume 48, Issue 11, November 2005
External links
- A New Paradigm for Computation. Los Angeles ACM Chapter Meeting, December 1, 1999.