0
$\begingroup$

I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking or rewriting, that is you can only move right and read the string in the order it is presented.

To simulate a PDA however I am not sure what restrictions we could apply. I was thinking allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA but I am not sure if that is a correct statement or how I would prove the equivalence of the two.

$\endgroup$
  • $\begingroup$ Hint: prove that with backtracking and no rewriting, a Turing machine can only extract a finite number of bits of information from the input, and therefore can only recognize regular languages. If the input is interleaved with rewritable cells, the machine is Turing complete again. $\endgroup$ – Yonatan N Dec 8 '18 at 1:36
  • $\begingroup$ @YonatanN how could I extend that to context free languages? $\endgroup$ – Mitchel Paulin Dec 8 '18 at 4:43
0
$\begingroup$

The basic idea is simple. Just make a Turing machine behave like a DFA or PDA. There are multiple ways.

How to make Turing machines have the same power as DFAs?

  • Here is a straightforward way as said in the question. We will not allow them to write on the tape. We will only allow them to read the input in one direction. In that way, they literally become DFAs.

  • In fact, we do not have to regulate how they read the input. We can simply use read-only Turing machines, which are equivalent to DFAs in power.

How to make Turing machines have the same power as PDAs?

  • Let us consider Turing machines with two tapes. One read-only tape with the input, which can only be read sequentially. Another tape that will be treated as a stack. Now you can see they are literally PDAs.
  • Suppose we are interested in simulating each PDA individually. The existence of such a TM is proven here.

There are many type of PDAs, such as deterministic or nondeterministic, accepting by final states or empty stack, even various generalized version. It should not be too difficult to see how they can be simulated by Turing machines.

"Allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA." No, it does not. As mentioned above, read-only Turing machines are equivalent to DFAs in power. Here is the explanation from Wikipedia. The proof involves building a table which lists the result of backtracking with the control in any given state; at the start of the computation, this is simply the result of trying to move past the left endmarker in that state. On each rightward move, the table can be updated using the old table values and the character that was in the previous cell. Since the original head-control had some fixed number of states, and there is a fixed number of states in the tape alphabet, the table has fixed size, and can therefore be computed by another finite state machine. This machine, however, will never need to backtrack, and hence is a DFA.

$\endgroup$

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.