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):

Examples of algorithmic schemes include:

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.[1] 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 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.[2][3]

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)

References

  1. 1 2 Hintikka, Ja. and Mutanen, A. An Alternative Concept of Computability, in “Language, Truth, and Logic in Mathematics”, Dordrecht, pp. 174–188, 1998
  2. ↑ J. Schmidhuber (2000): "Algorithmic Theories of Everything"
  3. ↑ J. Schmidhuber (2002): http://www.idsia.ch/~juergen/kolmogorov.html "Hierarchies of generalized
Notes
  • 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
  • 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 Publishing 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
  • Burgin, Mark (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
  • 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
  • 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
  • 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. Mark (1967), Language Identification in the Limit (PDF) 10, Information and Control, pp. 447–474 
  • Hagar, A. and Korolev, A. (2007) "Quantum Hypercomputation – Hype or Computation?"
  • 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 Hromkovič, Design and Analysis of Randomized Algorithms, Springer, 2005
  • Kleene, Stephen C. (1952), Introduction to Metamathematics (First ed.), Amsterdam: North-Holland Publishing Company .
  • Kosovsky, N. K. (1981) Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, Leningrad State University 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"
  • [Kolmogorov] complexities and nonenumerable universal measures computable in the limit". International Journal of Foundations of Computer Science 13(4):587-612
  • 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
  • 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

This article is issued from Wikipedia - version of the Thursday, February 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.