Super-recursive algorithm

In computer science and computability theory, super-recursive algorithms are algorithms that are more powerful, i.e. can compute more, than Turing machines. The term was introduced by Mark Burgin to more adequately describe what contemporary computers are doing.

Definition

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. Super-recursive algorithms perform hypercomputations. However, not any hypercomputation can be performed by a super-recursive algorithm. Some of hypercomputations are defined by super-recursive algorithm, while other only by computational schemas as it is written in the book (Burgin, 2005). Thus, the concept of super-recursive algorithm is more restricted than than the concept hypercomputation. Examples of super-recursive algorithm are:

• inductive Turing machines, which perform computations similar to computations of Turing machines and produce their results after a finite number of steps.
• limit Turing machines, which perform computations similar to computations of Turing machines and but their final results are limits of their intermediate results.
• Evolutionary computers, which use DNA to produce the value of a function.

Examples of practical super-recursive algorithms are given in the Wikipedia article Algorithm and in the book of Burgin.

Inductive Turing machines form an important class of super-recursive algorithms because they satisfy all conditions in the definition of algorithm. Namely, each inductive Turing machines is a type of effective method in which a definite list of well-defined instructions for completing a task, when given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an end-state. The difference between an inductive Turing machine and a Turing machine is that to produce the result a Turing machine has to stop, while in some cases an inductive Turing machine can do this without stopping. Kleene called procedures that could run forever without stopping by the name calculation procedure or algorithm (Kleene 1952:137). Kleene also demanded that such an algorithm must eventually exhibit "some object" (Kleene 1952:137). This conditions is satisfied by inductive Turing machines as their results are exibited after a finite number of steps.

Relation to the Church–Turing thesis

Burgin demonstrates how such super-recursive algorithms as inductive Turing machines disprove the Church–Turing thesis. He proves furthermore that super-recursive algorithms could theoretically provide even greater efficiency gains than using quantum algorithms.

Theory of super-recursive algorithms encounters opposition in the mathematical community as it happened with many new theories. Unfortunately, those who criticize this theory, do not give valid arguments to support their claims. The only author who tried to give a grounded critic was a noted logician Martin Davis. He has argues that there are no problems with mathematical issue of Burgin's theory (Davis 2006, p. 128). However, he thinks that "it can be misleading regarding physical systems of the present and future" (Davis 2006, p. 128). To support this claim, Davis gives two arguments. First what bothers Martin is that there is no bound of time necessary to obtain the result. Second problem that he can see is that in order for a computational result to be useful one must be able to at least recognize that it is indeed the result sought. The first argument is also a problem for Turing machines as for them there is also no bound of time necessary to obtain the result. The second argument involves not the problem of what is computable but what is useful. However, different super-recursive algorithms are successfully used in practice. An example is given by an algorithm that verifies if there are more zeros than ones in an infinite random binary sequence, which is described in the Wikipedia article Algorithm

References

• Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690
  • Review, Martin Davis (2007), Bulletin of Symbolic Logic, v. 13 n. 2. [1]
• Mark Burgin, "The Rise and Fall of the Church-Turing Thesis"
• Mark Burgin, "Super-recursive algorithms as a tool for high performance computing", Proceedings of the High Performance Computing Symposium, San Diego, 1999, pp. 224-228
• Darko Roglic, "The universal evolutionary computer based on super-recursive algorithms of evolvability"
• Martin Davis (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science 3988 pp. 125–132.

External links

• A New Paradigm for Computation. Los Angeles ACM Chapter Meeting, December 1, 1999.