# What is the relationship between Turing Machines with a finite tape and Finite State Automata?

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?

• How many possible states will a Turing machine with a finite tape have? Commented Mar 31, 2015 at 16:21
• It will be finitely many but, as the below answer shows, that's not necessarily sufficient for drawing an equivalence. Commented Mar 31, 2015 at 16:27

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.

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