Abstract
Thes mn function defined in the iteration theorem is shown to be quite subelementary through the use of stateless Turing machines. This means that recursion theorems can be used subrecursively with no change in computational complexity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Kleene, S. C.,Introduction to Mathematics, D. Van Nostrand Company, Princeton, New Jersey, 1952.
Myhill, J., “Creative sets,”Zeit f. Math. Logik u. Grund. der Math. 1:97–108 (1955).
Rogers, H., Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
Rights and permissions
About this article
Cite this article
Lewis, F.D. Stateless turing machines and fixed points. International Journal of Computer and Information Sciences 10, 215–218 (1981). https://doi.org/10.1007/BF00996831
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00996831