Multi-Tape and Infinite-State Automata -- A Survey

A survey of machines which are more powerful
than finite automata and less powerful than general 
Turing machines is presented.  It is felt that the machines
in this category are as closely related to 
digital computers as either the finite automata or the
unrestricted Turing machines.  Intermediate machines 
can be created by adjoining on infinite-state memory
to a finite-state machine and then performing any 
or all of the following: (1) restrict the manner in
which the unbounded portion of the memory can be 
accessed, (2) bound the number of steps allowed for a
computation by some increasing recursive function 
of the length of the input, (3) restrict the total amount
of memory available in the same manner.  Examples 
from all three classes and their properties are discussed.

CACM December, 1965

Fischer, P. C.

CA651215 JB March 6, 1978  3:24 PM

1154	5	1154
1154	5	1154
1154	5	1154