Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Super-recursive algorithm
Generalization of ordinary algorithms that compute more than Turing machines

In computability theory, super-recursive algorithms are proposed as a generalization of algorithms that compute beyond the capabilities of Turing machines. Introduced by Mark Burgin in his book Super-recursive algorithms, these theoretical models suggest possibilities for computations that exceed conventional limits. Burgin claims such algorithms can challenge the Church–Turing thesis, although this view remains controversial and is not broadly accepted within the mathematical community.

We don't have any images related to Super-recursive algorithm yet.
We don't have any YouTube videos related to Super-recursive algorithm yet.
We don't have any PDF documents related to Super-recursive algorithm yet.
We don't have any Books related to Super-recursive algorithm yet.
We don't have any archived web articles related to Super-recursive algorithm yet.

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 Δ 2 0 {\displaystyle \Delta _{2}^{0}} 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)