Recursive turing machines †
- 1 January 1977
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 6 (1) , 3-31
- https://doi.org/10.1080/00207167708803124
Abstract
The Turing machine model is extended to allow for recursive calls and the basic theory of these machines is developed. The model is also used to study the following additional topics: The time and storage needed to implement recursive algorithms by non-recursive algorithms, the storage needed to implement non-deterministic algorithms by deterministic algorithms, and the implementation of recursive algorithms by means of stack machines. Some attention is given to time bounds but the emphasis is on storage-bounded computations.Keywords
This publication has 2 references indexed in Scilit:
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970