Super-recursive algorithm

From Wikipedia, the free encyclopedia

 The neutrality and factual accuracy of this article are disputed.
Please see the relevant discussion on the talk page. (April 2008)

In computer science and computability theory, super-recursive algorithm is a term coined by Mark Burgin, a visiting scholar in the mathematics department at UCLA.[1]. The term is used to describe ideas in computability theory not covered by traditional Turing machines, but the usage is controversial.

Contents

[edit] Initial discussion

Burgin defines the term super-recursive algorithm as follows:

Any class of algorithms that is more powerful than the class of recursive algorithms (such as Turing machines) is called a class of superrecursive algorithms.[1]

However, in that source, Burgin had not, at the point of definition, defined any particular measures of "power". Moreover, it has been claimed, by reference to the same source (see below, and algorithm, where it is cited as being on p.107, rather than p.108), that Burgin offers another different definition, one that draws the distinction from Turing machines qualitatively rather than quantitatively:

"a class of algorithms in which it is possible to compute functions not computable by any Turing machine"[2].

Burgin's work on this topic has been briefly mentioned by Selim Akl (but only under the name "hypercomputation", which Burgin defines in his own terms as well, and only cited among other authors who might have different definitions of "hypercomputation")[3]. The term is mentioned once in a paper by Eugene Eberbach and Peter Wegner[4] and is presumably used more extensively in a few other papers Eberbach co-authored with Mark Burgin. Peter Kugel defended the concept in a Communications of the ACM article[5]. Jan van Leeuwen, Hava Siegelmann, and Jiri Wiedermann have also mentioned either the term "super-recursive algorithm" or cited Burgin when mentioning "hypercomputation".[citation needed]

Burgin's motivation for introducing and developing the concept appears to be his hope that it will unleash vast computing power. As he writes in his monograph:

One of the basic stereotypes for algorithms is that an algorithm has to stop when it gives a result. This is the main restriction hindering the development of computers. When we understand that computation can go on, but we can get what we need, we then go beyond our prejudices, and immensely extend computing power, introducing super-recursive algorithms.[6]

However, where computer science relies on definitions of (or constraints on) algorithms requiring termination, it is not a "stereotype". Rather, it is for purposes of analyzing algorithmic time complexity for achieving a final result, or proving whether or not an algorithm can terminate with a final result. Burgin speaks of understanding "that computation can go on", as if this insight would stimulate the development of new algorithms that do useful work without termination. However, he makes no mention of the field of anytime algorithms, which are interrupted for whatever answer they might have available at the time. Anytime algorithms are typically terminated after interruption, but not necessarily; in the real-time (or time-limited) applications where they are most useful, a future, more refined answer might be called for later, in which case restarting the anytime algorithm from scratch would be uneconomical. Anytime algorithms (by that name) have been a topic of serious study since as early as 1986.[7][8]

Burgin presents no evidence for any breakthrough in computing power that will become possible with acceptance of this concept. He presents no evidence that ignorance of a concept of super-recursive algorithm has hindered any practitioner in computer science or engineering from innovating in any area where improvements in computational power have been found. 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. Somehow, despite what Burgin calls a "prejudice" for algorithms that terminate, the developers of these applications were able to provide the needed value of such programs without resort to any concept of super-recursive algorithm. The relative paucity of references to "super-recursive algorithm" outside publications written, co-authored or (co-)edited by Mark Burgin suggests that the field of computer science has so far found concept uselessly general, at best.

[edit] 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: 108). Super-recursive algorithms are closely related to hypercomputation, which Burgin defines as a "computational process (including processes of input and output) that cannot be realized by recursive algorithms." (Burgin 2005: 108). 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, says Burgin, yields three classes of algorithms: subrecursive, recursive and super-recursive algorithms.

[edit] Examples

Examples of classes of super-recursive algorithms, according to Burgin (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)
  • 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)

According to Burgin, 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 claimed examples of practical super-recursive algorithms, see algorithm and the book of Burgin.

Examples of what Burgin claims are classes of subrecursive algorithms include:

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

[edit] Inductive Turing machines

Burgin says that Inductive Turing machines (a term of his own invention, suggested by "inductive inference machines") form an important class of super-recursive algorithms because they satisfy all conditions in his definition of algorithm. 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 required that such an algorithm 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, however (in his view, at least) inductive Turing machines may not be able to tell at which step the result has been obtained, which calls into question whether his inductive Turing machine meets Kleene's requirements.

Simple inductive Turing machines are equivalent to other models of computation.[citation needed] More advanced inductive Turing machines are much more powerful.[citation needed] 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.[citation needed] However, simple inductive Turing machines and general Turing machines give direct constructions of computing automata in comparison with trial and error predicates, limiting recursive functions and limiting partial recursive functions.[citation needed] 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.[citation needed]

Many confuse computations of inductive Turing machines with non-stopping computations or with infinite computations.[citation needed] First, some of computations of inductive Turing machines halt.[citation needed] As in the case of conventional Turing machines, some halting computations give the result, while others do not give.[citation needed] Second, some non-stopping computations of inductive Turing machines give results, while others do not give.[citation needed] Rules of inductive Turing machines determine when a computation (stopping or non-stopping) gives a result. [This contradicts the statement above, that "inductive Turing machines may not be able to tell at which step the result has been obtained"] In contrast to the widespread misconception[citation needed], if an inductive Turing machine gives a result, it gives the result after a finite number of steps.[citation needed]

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.[citation needed] The second distinction is that a conventional Turing machine always informs (by halting) 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[citation needed]), 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.[citation needed] 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.

[edit] Relation to the Church–Turing thesis

Based on a definition of algorithm more general than the commonly accepted definition, Burgin argues that super-recursive algorithms such as inductive Turing machines disprove the Church–Turing thesis. He argues furthermore that super-recursive algorithms could theoretically provide even greater efficiency gains than 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)

[edit] References

  1. ^ Burgin, Mark (2004). Super-recursive algorithms. Springer, p.108. ISBN 0387955690. 
  2. ^ (Burgin 2005: 108), very likely quoted in error by User:Multipundit unless it comes from another edition of the monograph.[citation needed]
  3. ^ Selim Akl, The Myth of Universal Computation, [[]], 2005. in Vajtersic, et al. (eds), M. (2005). Parallel Numerics '05, pp. 167-192. 
  4. ^ Eberbach, Eugene; Peter Wegner. "Beyond Turing Machines". 
  5. ^ Kugel, Peter (November 2005). "It's time to think outside the computational box". Communications of the ACM 11 (48). ACM. 
  6. ^ Burgin 2005, p.108
  7. ^ Boddy, M, Dean, T. 1989. "Solving Time-Dependent Planning Problems". Technical Report: CS-89-03, Brown University.
  8. ^ 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.
  • 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, S. Smale, Complexity and real computation, Springer 1998
  • 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
  • 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
  • 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
  • Kleene, Stephen C. (First Edition 1952), Introduction to Metamathematics, Amsterdam: North-Holland .
  • 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
  • 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
  • Jirí 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

[edit] External links