Super-recursive algorithm

In computability theory, super-recursive algorithms are a generalization of ordinary 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. Turing machines and other mathematical models of conventional algorithms allow researchers to find properties of recursive algorithms and their computations. In a similar way, mathematical models of super-recursive algorithms, such as inductive Turing machines, allow researchers to find properties of super-recursive algorithms and their computations.

Burgin, as well as other researchers (including Selim Akl, Eugene Eberbach, Peter Kugel, Jan van Leeuwen, Hava Siegelmann, Peter Wegner, and Jiří Wiedermann) who studied different kinds of super-recursive algorithms and contributed to the theory of super-recursive algorithms, have argued that super-recursive algorithms can be used to disprove the Church-Turing thesis, but 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 closely related to hypercomputation
in a way similar to the relationship between ordinary computation and ordinary algorithms. Computation is a process, while an algorithm is a finite constructive description of such a process. Thus a super-recursive algorithm defines a "computational process (including processes of input and output) that cannot be realized by recursive algorithms." (Burgin 2005: 108). A more restricted definition demands that hypercomputation solves a supertask (see Copeland 2002; Hagar and Korolev 2007).

Super-recursive algorithms are also related to algorithmic schemes, 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, e.g., inductive Turing machines, while other types of hypercomputation are directed by algorithmic schemas, e.g., infinite time Turing machines. This explains how works on super-recursive algorithms are related to hypercomputation and vice versa. According to this argument, super-recursive algorithms are just one way of defining a hypercomputational process.

Examples

Examples of super-recursive algorithms include (Burgin 2005: 132):
* limiting recursive functions and limiting partial recursive functions (E.M. Gold 1965)
* trial and error predicates (Hilary Putnam 1965)
* inductive inference machines (Carl Smith)
* inductive Turing machines, which perform computations similar to computations of Turing machines and produce their results after a finite number of steps (Mark Burgin)
* limit Turing machines, which perform computations similar to computations of Turing machines but their final results are limits of their intermediate results (Mark Burgin)
* trial-and-error machines (Ja. Hintikka and A. Mutanen 1998)
* general Turing machines (J. Schmidhuber)
* Internet machines ( van Leeuwen, J. and Wiedermann, J.)
* evolutionary computers, which use DNA to produce the value of a function (Darko Roglic)
* fuzzy computation (Jirí Wiedermann 2004)
* evolutionary Turing machines (Eugene Eberbach 2005)

Examples of algorithmic schemes include:

* Turing machines with arbitrary oracles (Alan Turing)
* Transrecursive operators (Borodyanskii and Burgin)
* machines that compute with real numbers (L. Blum, F. Cucker, M. Shub, and S. Smale 1998)
* neural networks based on real numbers (Hava Siegelmann 1999)

For examples of practical super-recursive algorithms, see the book of Burgin.

Inductive Turing machines

Inductive Turing machines implement an important class of super-recursive algorithms. An inductive Turing machine is a definite list of well-defined instructions for completing a task which, when given an initial state, will proceed through a well-defined series of successive states, eventually giving the final result. The difference between an inductive Turing machine and an ordinary Turing machine is that an ordinary Turing machine must stop when it has obtained its result, while in some cases an inductive Turing machine can continue to compute after obtaining the result, 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 that this condition is satisfied by inductive Turing machines, as their results are exhibited after a finite number of steps. The reason that inductive Turing machines cannot be instructed to halt when their final output is produced is that in some cases inductive Turing machines may not be able to tell at which step the result has been obtained.

Simple inductive Turing machines are equivalent to other models of computation such as general Turing machines of Schmidhuber, trial and error predicates of Hilary Putnam, limiting partial recursive functions of Gold, and trial-and-error machines of Hintikka and Mutanen (1998). More advanced inductive Turing machines are much more powerful. There are hierarchies of inductive Turing machines that can decide membership in arbitrary sets of the arithmetical hierarchy (Burgin 2005). In comparison with other equivalent models of computation, simple inductive Turing machines and general Turing machines give direct constructions of computing automata that are thoroughly grounded in physical machines. In contrast, trial-and-error predicates, limiting recursive functions, and limiting partial recursive functions present only syntactic systems of symbols with formal rules for their manipulation. Simple inductive Turing machines and general Turing machines are related to limiting partial recursive functions and trial-and-error predicates as Turing machines are related to partial recursive functions and lambda calculus.

The non-halting computations of inductive Turing machines should not be confused with infinite-time computations (see, for example, Potgieter 2006). First, some computations of inductive Turing machines do halt. As in the case of conventional Turing machines, some halting computations give the result, while others do not. Even if it does not halt, an inductive Turing machine produces output from time to time. If this output stops changing, it is then considered the result of the computation.

There are two main distinctions between ordinary Turing machines and simple inductive Turing machines. The first distinction is that even simple inductive Turing machines can do much more than conventional Turing machines. The second distinction is that a conventional Turing machine will always determine (by coming to a final state) when the result is obtained, while a simple inductive Turing machine, in some cases (such as when "computing" something that cannot be computed by an ordinary Turing machine), will not be able to make this determination.

Schmidhuber's generalized Turing machines

A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π but still excludes most of the real numbers, because most cannot be described by a finite program. Traditional Turing machines with a write-only output tape cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can edit their output tape as well as their work tape. He defines the constructively describable symbol sequences as those that have a finite, non-halting program running on a generalized Turing machine, such that any output symbol eventually converges, that is, it does not change any more after some finite initial time interval. Schmidhuber (2000, 2002) uses this approach to define the set of formally describable or constructively computable universes or constructive theories of everything. Generalized Turing machines and simple inductive Turing machines are two classes of super-recursive algorithms that are the closest to recursive algorithms (Schmidhuber 2000).

Relation to the Church–Turing thesis

The Church–Turing thesis in recursion theory relies on a particular definition of the term ''algorithm''. Based on definitions that are more general than the one commonly used in recursion theory, Burgin argues that super-recursive algorithms, such 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.

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 $\Delta^0_2$ 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)

See also

* Interactive computation

References

* Blum, L., F. Cucker, M. Shub, and S. Smale, '' Complexity and Real Computation'', Springer Publishing 1998
* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer.
**José Félix Costa
MR2246430 Review
in MathSciNet.
** Harvey Cohn (2005)
CR131542 (0606-0574) Review
in Computing Reviews
**Martin Davis (2007
Review
in '' Bulletin of Symbolic Logic'', v. 13 n. 2.
** Marc L. Smith (2006)
Review
in ''The Computer Journal'', Vol. 49 No. 6
**Review, Vilmar Trevisan (2005), Zentralblatt MATH, Vol. 1070. Revie
1070.68038

* Copeland, J. (2002) Hypercomputation, ''Minds and Machines'', v. 12, pp. 461–502
* Davis, Martin (2006),
The Church–Turing Thesis: Consensus and opposition
. Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
* Eberbach, E. (2005) "Toward a theory of evolutionary computation", ''BioSystems'' 82, 1-19
* Gold, E.M. Limiting recursion. '' J. Symb. Log.'' 10 (1965), 28-48.
*
* Hagar, A. and Korolev, A. (2007
"Quantum Hypercomputation – Hype or Computation?"

* Hintikka, Ja. and Mutanen, A. An Alternative Concept of Computability, in “Language, Truth, and Logic in Mathematics”, Dordrecht, pp. 174–188, 1998
* .
* Peter Kugel, "It's time to think outside the computational box", ''Communications of the ACM'', Volume 48, Issue 11, November 2005
* Petrus H. Potgieter, "Zeno machines and hypercomputation", ''Theoretical Computer Science'', Volume 358, Issue 1 (July 2006) pp. 23 – 33
* Hilary Putnam, "Trial and Error Predicates and the Solution to a Problem of Mostowski". ''Journal of Symbolic Logic'', Volume 30, Issue 1 (1965), 49-57
* Darko Roglic,
The universal evolutionary computer based on super-recursive algorithms of evolvability

* Hava Siegelmann, ''Neural Networks and Analog Computation: Beyond the Turing Limit'', Birkhäuser, 1999, {{isbn, 0817639497
* Turing, A. (1939) Systems of Logic Based on Ordinals, '' Proc. Lond. Math. Soc.'', Ser.2, v. 45: 161-228
* van Leeuwen, J. and Wiedermann, J. (2000a) ''Breaking the Turing Barrier: The case of the Internet'', Techn. Report, Inst. of Computer Science, Academy of Sciences of the Czech Republic, Prague
* Jiří Wiedermann, Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, ''Theoretical Computer Science'', Volume 317, Issue 1-3, June 2004
* Jiří Wiedermann and Jan van Leeuwen, "The emergent computational potential of evolving artificial living systems", ''AI Communications'', v. 15, No. 4, 2002

Further reading

* Akl, S.G., Three counterexamples to dispel the myth of the universal computer, ''Parallel Processing Letters'', Vol. 16, No. 3, September 2006, pp. 381 – 403.
* Akl, S.G., The myth of universal computation, in: Parallel Numerics, Trobec, R., Zinterhof, P., Vajtersic, M., and Uhl, A., Eds., Part 2, ''Systems and Simulation'', University of Salzburg, Salzburg, Austria and Jozef Stefan Institute, Ljubljana, Slovenia, 2005, pp. 211 – 236
* Angluin, D., and Smith, C. H. (1983) Inductive Inference: Theory and Methods, ''Comput. Surveys'', v. 15, no. 3, pp. 237–269
* Apsïtis, K, Arikawa, S, Freivalds, R., Hirowatari, E., and Smith, C. H. (1999) On the inductive inference of recursive real-valued functions, ''Theoretical Computer Science'', 219(1-2): 3—17
* Boddy, M, Dean, T. 1989. "Solving Time-Dependent Planning Problems". Technical Report: CS-89-03, Brown University
* Burgin, M. "Algorithmic Complexity of Recursive and Inductive Algorithms", ''Theoretical Computer Science'', v. 317, No. 1/3, 2004, pp. 31–60
* Burgin, M. and Klinger, A. Experience, Generations, and Limits in Machine Learning, ''Theoretical Computer Science'', v. 317, No. 1/3, 2004, pp. 71–91
* Eberbach, E., and Wegner, P., "Beyond Turing Machines", ''Bulletin of the European Association for Theoretical Computer Science'' (EATCS Bulletin), 81, Oct. 2003, 279-304
* S. Zilberstein, Using Anytime Algorithms in Intelligent Systems, "AI Magazine", 17(3):73-83, 1996

External links

A New Paradigm for Computation
Los Angeles ACM Chapter Meeting, December 1, 1999.
*
Anytime algorithm
' from FOLDOC

Algorithms
Hypercomputation
Theory of computation