retagged by
310 views
0 votes
0 votes
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.
retagged by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
0 answers
4