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?

  • $\begingroup$ How many possible states will a Turing machine with a finite tape have? $\endgroup$ Commented Mar 31, 2015 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$ Commented Mar 31, 2015 at 16:27

1 Answer 1


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.

  • $\begingroup$ Your answer for the bounded tape was exactly what I was looking for . Thank you! $\endgroup$ Commented Mar 31, 2015 at 16:24
  • $\begingroup$ @Shaull in bounded shell infinite-regular languages acceptance is possible? $\endgroup$
    – A. H.
    Commented Jul 14, 2022 at 13:21
  • $\begingroup$ @user19121278 - could you elaborate? I didn't understand your question. Also, is "shell" a typo? $\endgroup$
    – Shaull
    Commented Jul 16, 2022 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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