Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-02T22:53:57.117Z Has data issue: false hasContentIssue false
  • English
  • Français

Limiting recursion

Published online by Cambridge University Press:  12 March 2014

E. Mark Gold
E. Mark Gold*
Affiliation:
Lear Siegler, Incorporated/Research Laboratories, Santa Monica, California
Get access Rights & Permissions [Opens in a new window]

Extract

A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in the limit if, after some finite point in the sequence, all the guesses are correct and the same (in case there is more than one correct answer). Functions, sets, and functionals which are decidable by such infinite algorithms will be called limiting recursive. These, together with classes of objects which can be identified in the limit, are the subjects of this report.

Without qualification, set will mean set of numbers; function will mean number-theoretic function of 1 variable, possibly partial; functionals will take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional, x will invariably stand for a numerical variable; φ for a function variable; g for a guess (a number); n for the numerical variable which indexes the guesses, referred to as the time.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 30 , Issue 1 , March 1965 , pp. 28 - 48
Copyright
Copyright © Association for Symbolic Logic 1965

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Brzozowski, J. A., Properties of regular expressions and state diagrams, Technical report no. 15, Department of electrical engineering, Digital systems laboratory, Princeton University, 1962.Google Scholar
[2]Davis, Martin, Computability and unsolvability, McGraw Hill, 1958.Google Scholar
[3]Gill, A., State-identification experiments in finite automata, Information and control, vol. 4 (1961), pp. 132–154.CrossRefGoogle Scholar
[4]Gold, E Mark, Language identification in the limit, RM-4136-PR, the RAND Corporation, 1964.Google Scholar
[5]Grzegorczyk, A., Computable functionals, Fundamenta mathematica, vol. 42 (1955), pp. 168–203; see comments by S. C. Kleene in Indagationes mathematicae, vol. 18 (1956), pp. 275–280.CrossRefGoogle Scholar
[6]Kleene, S. C., Recursive functions and intuitionistic mathematics, Proceedings of the International Congress of Mathematicians, 1950, vol. 1, 679–685.Google Scholar
[7]Kleene, S. C., Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar
[8]Moore, E. F., Gedanken-experiments on sequential machines, Automata studies, Princeton University Press, 1956.Google Scholar
[9]Smullyan, R., Theory of formal systems, Princeton University Press, 1961.CrossRefGoogle Scholar
[10]Stearns, R. E. and Hartmanis, J., Regularity preserving modification of regular expressions, Information and control, vol. 6 (1963), pp. 55–69.CrossRefGoogle Scholar