super-recursive algorithm
{{short description|Generalization of ordinary algorithms that compute more than Turing machines}}
{{notability|date=February 2024}}
{{No footnotes|date=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
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
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
- Burgin, Mark (2005), Super-recursive algorithms, Monographs in computer science, Springer. {{isbn|0-387-95569-0}}
- Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
- Peter Kugel, [https://www.researchgate.net/publication/220425557_It%27s_time_to_think_outside_the_computational_box "It's time to think outside the computational box"], Communications of the ACM, Volume 48, Issue 11, November 2005
External links
- [https://www.la-acm.org/Archives/laacm9912.html A New Paradigm for Computation]. Los Angeles ACM Chapter Meeting, December 1, 1999.