Problem Detail: I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I’ve been unable to find this confirmed anywhere on the internet. Is this actually the case or am I misremembering?
Asked By : Jesse Berlin
Answered By : Shaull
It depends what you mean by “finite tape”. If you bound the length of the tape by some function of the input, then no – you can recognize non-regular languages. For example, consider LBAs. But if you mean a bounded tape, where the tape has $k$ cells for some fixed $k$, then yes – you indeed get a model which is equivalent to DFAs. To prove this, consider what information you need to determined the future of a run of a TM: you need the contents of the tape, the location of the head, and the state. If the tape has a constant number of cells, and the alphabet is fixed, then you have a constant number of configurations, which you can encode as states of a finite automaton.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40911
