10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How many possible states will a Turing machine with a finite tape have? $\endgroup$ – Dave Clarke Mar 31 '15 at 16:21
  • $\begingroup$ It will be finitely many but, as the below answer shows, that's not necessarily sufficient for drawing an equivalence. $\endgroup$ – Jesse Berlin Mar 31 '15 at 16:27
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your answer for the bounded tape was exactly what I was looking for . Thank you! $\endgroup$ – Jesse Berlin Mar 31 '15 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.