0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Finite state machines can definitely go into infinite loops. $\endgroup$ – reinierpost Jan 6 at 19:04
2
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So should we at least have restriction that the fixed length tape should be read only for TM to be DFA? or in other words having just fixed length tape does not suffice for TM to become equivalent to DFA, that fixed length tape should be read only for TM to be equivalent to DFA? (Because, I guess, if its read-write two way tape, then TM may go in loop and wont be equal to DFA.) I feel (1) Fixed size one way read write tape TM = DFA (2) Fixed size two way read only tape TM = DFA (3) Fixed size two way read write tape TM > DFA. Is it right? $\endgroup$ – anir Jan 6 at 14:28
  • $\begingroup$ Yes, if the input tape can be written on, then you suddenly have $O(n)$ space, and you get a Linear Bounded Automaton (LBA), which can do much stronger things than regular languages (e.g. $a^nb^n$). If the input tape has fixed size, then you can only read finitely many inputs, so the whole model doesn't really make sense, since it deals only with finite/co-finite languages. $\endgroup$ – Shaull Jan 6 at 15:31
1
$\begingroup$

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-

  1. limited memory= Finite automata
  2. one time input scan + unlimited memory= push down automata
  3. multiple tape scan + memory which is linearly proportional to input size= Linear bounded automata
  4. multiple tape scan +unlimited memory= Turing machine

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ should it be limited "read only" memory = Finite automata? Because if its two way read write memory then TM might go in infinite loop. I feel: (1) Fixed size one way read write tape TM = DFA (2) Fixed size two way read only tape TM = DFA (3) Fixed size two way read write tape TM > DFA. Is it right? $\endgroup$ – anir Jan 6 at 14:32
  • $\begingroup$ @anir, please look at the edit. $\endgroup$ – john chakder Jan 6 at 16:49

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.