Super-recursive algorithm: Difference between revisions

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 to more adequately describe what contemporary computers are doing and how people use computers. Indeed, since mid 1980's, the AI community has produced a large body of work on anytime algorithms for solving such problems as real-time search, constraint satisfaction, planning and scheduling, and diagnosis (Horvitz 1986; Boddy and Dean 1989; Zilberstein 1996). Traditional algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. An example is the Newton-Raphson iteration applied to finding the square root of a number. This iteration cannot be modeled by a Turing machine and demands more powerful mathematical models, such as limit Turing machines. Theoretical results show that limit Turing machines are more powerful than Turing machines and thus are super-recursive algorithms. Thus, super-recursive algorithms exist not only in theory but are already used in computing practice. The book "Super-recursive algorithms" by Burgin develops the theory of super-recursive algorithms, describing many mathematical models of super-recursive algorithms. 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 (Selim Akl, Eugene Eberbach, Peter Kugel, Jan van Leeuwen, Hava Siegelmann, Peter Wegner, and Jirí Wiedermann, to mention but a few) who studied different kinds of super-recursive algorithms and contributed to the theory of super-recursive algorithms, have argued that there are super-recursive algorithms that disprove the Church-Turing thesis, but this point of view is often criticized within the mathematical community.

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 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). Burgin argues this conditions 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. More advanced inductive Turing machines are much more powerful. It is proved (Burgin, 2005) that limiting partial recursive functions, trial and error predicates, general Turing machines, and simple inductive Turing machines are equivalent models of computation. However, simple inductive Turing machines and general Turing machines give direct constructions of computing automata, which are thoroughly grounded in physical machines. In contrast, trial and error predicates, limiting recursive functions and limiting partial recursive functions present 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 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 of computations of inductive Turing machines halt. As in the case of conventional Turing machines, some halting computations give the result, while others do not give. Second, some non-stopping computations of inductive Turing machines give results, while others do not give. 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 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 give results (when it happens) always after a finite number of steps (in finite time) in contrast to 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 machines can do much more than conventional Turing machines. The second distinction is that a conventional Turing machine always informs (by halting or by coming to a final state) when the result is obtained, while a simple inductive Turing machine in some cases does inform about reaching the result, while in other cases (where the conventional Turing machine is helpless), it does not inform. People have an illusion that a computer always itself informs (by halting or by other means) when the result is obtained. In contrast to this, users themselves have to decide in many cases whether the 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 it may be impossible to predict the convergence time itself by a halting program, otherwise the halting problem could be solved. Schmidhuber 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

Whether the Church–Turing thesis is true or not depends on the definition of algorithm. Based on definitions that are more general than the most popular ones, 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 _{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)

However, stochastic algorithms and their particular case – randomized algorithms – are useful but does not allow one to recognize in all cases that the computational result is indeed the result sought (Hromkovic 2005).

Cockshott and Michaelson (2007) also contest the claims that it is possible to overcome the Church–Turing thesis by some models of super-recursive algorithms, or super-Turing models of algorithms. In Section 2.5, they discuss "what might be required to overthrow the Church–Turing thesis." However, their discussion does not encompass all models of super-recursive algorithms, and it is possible to check that inductive Turing machines satisfy all conditions "required to overthrow the Church–Turing thesis."

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 MR2246430.
  • Review, Harvey Cohn (2005), "Computing Reviews", Review CR131542 (0606-0574)
  • Review, Martin Davis (2007), Bulletin of Symbolic Logic, v. 13 n. 2. Online version
  • Review, Marc L. Smith (2006), "The Computer Journal", Vol. 49 No. 6 Online version
  • Review, Vilmar Trevisan (2005), Zentralblatt MATH, Vol. 1070. Review 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
• Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, v. 50, No. 2, 2007, pp. 232-247
• Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461-502
• Martin Davis (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
• Eberbach, E., and Wegner, P., Beyond Turing Machines, Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304
• 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
• Jurai Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005
• Kleene, Stephen C. (First Edition 1952), Introduction to Metamathematics, Amsterdam: North-Holland {{citation}}: Check date values in: |year= (help)CS1 maint: year (link).
• 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, "The universal evolutionary computer based on super-recursive algorithms of evolvability"
• Schmidhuber, J. Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612, 2002
• 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

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