Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I read following:
Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.
Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if it keeps moving from left to right and finite state machine does never go in such infinite loops. So, do we also need restrictions like "only right head movements are allowed" along with finite tape to turn Turing Machine to finite state automaton?
Yes, this is (kind of) correct, in the following sense:
The set of languages that can be recognized by Turing Machines with a fixed tape is equivalent to the set of regular languages (i.e. the set of languages recognizable by finite automata).
The reason behind this is that such Turing Machines have a finite number of configurations, which is independent from the input.
Note that crucially, for this to hold we need one tape for the input which is read-only, and a fixed-space working tape.
A bit more precisely, for such a TM, we can construct a 2-way DFA, by having a state for every possible configuration of the TM, as well as a 2-way read only input tape. The latter model is equivalent to DFAs, by a clever construction using "crossing sequences".
An important observation, however, is that these machines can be far more succinct than their equivalent DFAs (or even NFAs).
Yup, It does behave like a finite state machine.
if for (every permutation in tape string, every current head position, every next move) you create a unique state, you are besically creating a DFA like mechanism, as (next move/tape write) is determined by those variables and you have a state for every possible combination. And as the tape is finite, the no of state will also be finite.
the thing is-
so, you might think that limited memory turing maching behaves like a Linear bounded automata but as the memory is limited and not growing with respect to input, it will not be as powerful as LBA but just a Finite automata.
see, if the input is given in the tape itself . so, with larger input, the tape length has to increase. which means you can scan the input multiple time+ you have space (memory) linearly dependent to the input length. so, the whole setup will be as powerful as LBA. If the input is given some other way and not in the "fixed sized" tape, it will be a DFA only.
But by the "finite tape" in the qustion, I assume you have some some fixed no of cell (K) irrespect to the input length. so for an input larger then K simbols, you have to provide some other way as the tape can hold only K simbols. in this scenario, the TM will not be more powerful than a DFA even if you can write the tape (as number of elements in $\Sigma$ is finite so only finite tape configuration is possible).
