# 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? – Dave Clarke Mar 31 '15 at 16:21
• It will be finitely many but, as the below answer shows, that's not necessarily sufficient for drawing an equivalence. – Jesse Berlin Mar 31 '15 at 16:27

## 1 Answer

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! – Jesse Berlin Mar 31 '15 at 16:24