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.
