Super-recursive algorithm

In computer science and computability theory, super-recursive algorithms are 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 limiting recursive functions, limiting partial recursive functions, trial and error predicates, inductive Turing machines, and limit Turing machines, allow researchers to find properties of super-recursive algorithms and their computations.

Burgin, as well as other researches (including Selim Akl, Eugene Eberbach, Peter Kugel, Jan van Leeuwen, Hava Siegelmann, Peter Wegner, and Jirí 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 general sense, which Burgin defines as 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, i.e., task that needs infinite resources, such as time, memory or precision, for computation (see Copeland 2002; Hagar and Korolev 2007).

As a result, some types of hypercomputation in a general sense are controlled by super-recursive algorithms, e.g., inductive Turing machines, while other types 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. Thus, 'hypercomputation' and 'super-recursive algorithm' are not different names of the same things. They are connected but essentially different terms.

However, it is important not to confuse hypercomputation and super-recursive algorithms. The main difference is the same as the difference between computation and algorithm. Computation is a process, while an algorithm is a finite constructive description of such a process. In spite of this clear distinction, some researchers do not differentiate these two concepts. For instance, Davis (2006; 128) writes, "… this kind of computation should be regarded as a "super-recursive algorithm."

Super-recursive algorithms are also related to algorithmic schemes. The term algorithmic scheme is much more general than the term "super-recursive algorithm" and Burgin argues (2005: 115) that it's necessary to make a clear distinction between super-recursive algorithms and those algorithmic schemes that are not algorithms.The term subrecursive algorithm has been also used by different authors, for example, (Axt, 1959; Kosovsky, 1981; Campagnolo, Moore, and Costa, 2000). A subrecursive class of algorithms is a class of algorithms in which it is impossible to compute all functions computable by Turing machines. This yields three big classes of algorithms: "subrecursive", "recursive" and "super-recursive algorithms".

Examples

Examples of super-recursive algorithms include (Burgin 2005: 132):
* limiting recursive functions and limiting partial recursive functions (E.M. Gold)
* trial and error predicates (Hilary Putnam)
* 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)
* 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)
* evolutionary Turing machines (Eugene Eberbach)

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)
* neural networks based on real numbers (Hava Siegelmann)

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

Examples of subrecursive algorithms include:

* primitive recursive functions
* recursive functions
* finite automata
* pushdown automata
* monotone Turing machines

Inductive Turing machines

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 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 giving the final result. 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). Burgin argues that this condition is satisfied by inductive Turing machines, as their results are exhibited after a finite number of steps, but 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. More advanced inductive Turing machines are much more powerful. There are hierarchies of inductive Turing machines that can compute 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.

Many confuse the computations of inductive Turing machines with non-stopping computations or with infinite-time computations (see, for example, Potgieter 2006; Zenil and Hernandez-Quiroz 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. Second, some non-stopping computations of inductive Turing machines give results, while others do not. Rules of inductive Turing machines determine when a computation (stopping or non-stopping) gives a result. Namely, an inductive Turing machine produces output from time to time and once this output stops changing, it is considered the result of the computation. It is necessary to know that descriptions of this rule in some papers are incorrect. For instance, Davis (2006: 128) formulates the rule when a result is obtained without stopping as "… once the correct output has been produced any subsequent output will simply repeat this correct result." Third, in contrast to the widespread misconception, inductive Turing machines will always give results (when they occur) after a finite number of steps (in finite time), unlike infinite and infinite-time computations.

There are two main distinctions between conventional Turing machines and simple inductive Turing machines. The first distinction is that even simple inductive Turing machine can do much more than conventional Turing machines. The second distinction is that a conventional Turing machine will always inform (by halting or by coming to a final state) when the result is obtained, while a simple inductive Turing machine, in some cases (where the conventional Turing machine is helpless), will not inform. People have an illusion that a computer will always inform (by halting or by other means) when the result is obtained. However, users often have to decide whether a computed result is what they need or it is necessary to continue computations. Indeed, everyday desktop computer applications like word processors and spreadsheets spend most of their time waiting in event loops and do not terminate until directed to do so by users.

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 pi but still excludes most of the real numbers, because most cannot be described by a finite program. Traditional Turing machines cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can. 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. Due to limitations first exhibited by Kurt Gödel (1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the halting problem could be solved. 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.

Relation to the Church–Turing thesis

The Church–Turing thesis in recusrion 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)

References

* 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, "Theoret. Computer Science", 219(1-2): 3—17
* Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, "Transactions of the American Mathematical Society", v. 92, pp. 85-105
* Blum, L., and Blum, M. (1975) Toward a mathematical theory of inductive inference. "Information and Control" vol. 28, pp. 125-155
* Blum, L., F. Cucker, M. Shub, and S. Smale, "Complexity and real computation", Springer 1998
* Boddy, M, Dean, T. 1989. "Solving Time-Dependent Planning Problems". Technical Report: CS-89-03, Brown University
* Borodyanskii, Yu. M. and Burgin, M.S. (1994) Operations with Transrecursive Operators, Cybernetics and System Analysis, No. 4, pp. 3-11
* Mark Burgin (2005), "Super-recursive algorithms", Monographs in computer science, Springer. ISBN 0387955690
**Review, José Félix Costa, MathSciNet. Review [http://www.ams.org/mathscinet/search/publdoc.html?pg1=IID&s1=193826&r=3&mx-pid=2246430 MR2246430] .
**Review, Harvey Cohn (2005), "Computing Reviews", Review [http://www.computingreviews.net/browse/browse_topics4.cfm?ccs_id=2376 CR131542 (0606-0574)]
**Review, Martin Davis (2007), "Bulletin of Symbolic Logic", v. 13 n. 2. [http://www.math.ucla.edu/~asl/bsl/1302/1302-004.ps Online version]
**Review, Marc L. Smith (2006), "The Computer Journal", Vol. 49 No. 6 [http://comjnl.oxfordjournals.org/cgi/reprint/49/6/762-a.pdf Online version]
**Review, Vilmar Trevisan (2005), Zentralblatt MATH, Vol. 1070. Review [http://siba-sinmdb.unile.it/cgi-bin/zmen/ZMATH/en/quick.html?first=1&maxdocs=3&type=html&an=1070.68038&format=complete 1070.68038]
* Burgin, M. How We Know What Technology Can Do, "Communications of the ACM", v. 44, No. 11, 2001, pp. 82-88
* Burgin M., Universal limit Turing machines, "Notices of the Russian Academy of Sciences", 325, No. 4, (1992), 654-658
* Burgin, M. and Klinger, A. Three Aspects of Super-recursive Algorithms and Hypercomputation or Finding Black Swans, "Theoretical Computer Science", v. 317, No. 1/3, 2004, pp. 1-11
* 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
* Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91-109
* Copeland, J. (2002) Hypercomputation, " Minds and machines", v. 12, pp. 461-502
* Martin Davis (2006), " [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
* Eberbach, E. (2005) Toward a theory of evolutionary computation, "BioSystems" 82, 1-19
* Eberbach, E., and Wegner, P., Beyond Turing Machines, "Bulletin of the European Association for Theoretical Computer Science" (EATCS Bulletin), 81, Oct. 2003, 279-304
* Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme," "Monatshefte für Mathematik und Physik 38": 173-98.
* Gold, E.M. Limiting recursion. "J. Symb. Logic" 10 (1965), 28-48.
* Gold, E.M. (1967) Language Identification in the Limit, "Information and Control", v. 10, pp. 447-474
* Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation – Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
* Hintikka, Ja. and Mutanen, A. An Alternative Concept of Computability, in “Language, Truth, and Logic in Mathematics”, Dordrecht, pp. 174-188, 1998
* E.J. Horvitz. Reasoning about inference tradeoffs in a world of bounded resources. Technical Report KSL-86-55, Medical Computer Science Group, Section on Medical Informatics, Stanford University, Stanford, CA, March 1986
* Juraj Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005
*.
* Kosovsky, N. K. (1981) "Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms", LSU Publ., Leningrad
* 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. J. Symbolic Logic, Volume 30, Issue 1 (1965), 49-57
*Darko Roglic, " [http://arxiv.org/abs/0708.2686 The universal evolutionary computer based on super-recursive algorithms of evolvability] "
* J. Schmidhuber (2000): Algorithmic Theories of Everything http://arxiv.org/abs/quant-ph/0011122
* J. Schmidhuber (2002): Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612 http://www.idsia.ch/~juergen/kolmogorov.html
* Hava Siegelmann, "Neural Networks and Analog Computation: Beyond the Turing Limit", Birkhauser, 1999
* 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. Rep., 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
* Hector Zenil and Francisco Hernandez-Quiroz, On the possible computational power of the human mind, Worldviews, Science and Us, edited by Carlos Gershenson, Diederik Aerts and Bruce Edmonds, World Scientific, 2007, (arXiv:cs.NE/0605065v3)
* S. Zilberstein, Using Anytime Algorithms in Intelligent Systems, "AI Magazine", 17(3):73-83, 1996

External links

* [http://www.la-acm.org/Archives/laacm9912.html A New Paradigm for Computation] . Los Angeles ACM Chapter Meeting, December 1, 1999.
* " [http://foldoc.org/?anytime+algorithm Anytime algorithm] " from FOLDOC