Super-recursive algorithm
 | The topic of this article may not meet Wikipedia's general notability guideline. (February 2024) |
 | 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 posited as a generalization of hypercomputation: hypothetical algorithms that are more powerful, that is, compute more than Turing machines.
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
[edit]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, another novel concept from Burgin, 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.
Relation to the Church–Turing thesis
[edit]The Church–Turing thesis in recursion theory relies on a particular definition of the term algorithm. Based on his personal definitions that are more general than the one commonly used in recursion theory, Burgin argues that super-recursive algorithms 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
[edit]- Burgin, Mark (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
- Davis, Martin (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
- Peter Kugel, "It's time to think outside the computational box", Communications of the ACM, Volume 48, Issue 11, November 2005
External links
[edit]- A New Paradigm for Computation. Los Angeles ACM Chapter Meeting, December 1, 1999.