1
$\begingroup$

I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be false). Does anyone have a pointer to a reference?

$\endgroup$
4
$\begingroup$

A Turing Machine that can only move right can only read its input once, hence I don't see how it could be more powerful than a DFA.

It does have the ability to write to the tape, but it can't go back to read what it wrote, so this can't be used as memory. I seems that it's essentially equivalent to a Finite State Transducer, which are DFAs that have an output tape as well as input, but are no more powerful. In this case, the TM just happens to overwrite the input as it goes, rather than having a second tape.

$\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.