imported>Comp.arch at 22:15, 2 December 2024

2024-12-02T22:15:35Z

New page

{{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 [[algorithm]]s 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 [[algorithm]]s 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 (mathematician)|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 <math>\Delta^0_2</math> 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.

[[Category:Hypercomputation]]

Super-recursive algorithm - Revision history

imported>Comp.arch at 22:15, 2 December 2024