[Solved]: Right moving turing machine

Problem Detail: 

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?

Asked By : Al Learner

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18639