On computability by certain classes of restricted turing machines
- 1 October 1963
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The theory of abstract machines has been well developed for the finite automaton [RS] and the Turing machine [D]. More recently, machines intermediate in computing power between the above two classes of machines have been investigated. These machines have some form of unbounded memory, thus giving them more potential computing ability than the finite automata, but the access to the unbounded memory is restricted in some way so that they do not have the full power of a Turing machine. The two forms of restricted unbounded memory we shall consider here are the counter and the pushdown store.Keywords
This publication has 3 references indexed in Scilit:
- Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing MachinesAnnals of Mathematics, 1961
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959
- A Variant to Turing's Theory of Computing MachinesJournal of the ACM, 1957