Super-recursive algorithm

In computability theory, super-recursive algorithms provide a generalization of algorithms. The term was introduced by Mark Burgin to describe certain forms of hypercomputation. Burgin argues that they can be used to refute the Church–Turing thesis. However, Burgin's claim is strongly disputed by the mathematical community.

Definition

A super-recursive class of algorithms is a class of algorithm in which it is possible to compute functions not computable by any Turing machine. Super-recursive algorithms perform hypercomputation. However, not any hypercomputation can be performed by a super-recursive algorithm. Some types of hypercomputation are defined by super-recursive algorithm, while other only by computational schemas. Thus, the concept of super-recursive algorithm is more restricted than than the concept hypercomputation. Examples of super-recursive algorithm include:

• 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.
• Algorithms in the ordinary sense.

Inductive Turing machines form an important class of super-recursive algorithms because they satisfy many of the conditions in the definition of algorithm. Namely, each inductive Turing machine 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 run forever 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). Burgin argues this condition is satisfied by inductive Turing machines, as their results are exhibited after a finite number of steps. However, the machine cannot determine when the result is reached (or else it would be able to stop at that time).

Relation to the Church–Turing thesis

Burgin argues that super-recursive algorithms that lead to non-computable functions disprove the Church–Turing thesis. He argues furthermore that super-recursive algorithms could theoretically provide even greater efficiency gains than using quantum algorithms.

Martin Davis has argued that Burgin's work does not disprove the Church-Turing thesis, describing some of Burgin's claims as "misleading" (Davis 2006, p. 4).

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, "Super-recursive algorithms as a tool for high performance computing", Proceedings of the High Performance Computing Symposium, San Diego, 1999, pp. 224-228
• Mark Burgin, "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.
• Kleene, Stephen C. (First Edition 1952), Introduction to Metamathematics, Amsterdam: North-Holland {{citation}}: Check date values in: |year= (help)CS1 maint: year (link).

External links

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