-2
$\begingroup$

I assume no, because a Turing machine that can only move right feels like it is not a Turing machine. But, I wonder if I can add a Reset to the right moving Turing machine that resets the what head is pointing at all the way to the left of the TM. However, doesn't this make it left moving??

hmm...

$\endgroup$
6
  • $\begingroup$ Wow... A computer with a WOM (write only memory). That is gonna be a big hit on the computer market. Actually, we have plenty of devices with the same computing power, but adding a WOM is a so much fancier, $\endgroup$ – babou May 19 '15 at 23:02
  • $\begingroup$ If the story says only to the right, that is what it is. If the story does not allude to a reset button, you must assume there is none. BTW, this question was asked before ... you should check (you should have done it first): Power of variants of Turing machines - - your question will be closed as duplicate $\endgroup$ – babou May 19 '15 at 23:21
  • $\begingroup$ This question is a dup but the original question went unanswered except for hints. $\endgroup$ – Kyle Jones May 20 '15 at 0:14
  • 1
    $\begingroup$ @Sam No, please don't do that. It's bad enough that you're asking the same question a second time. But to then talk about deleting the first version after people have already taken the time to comment on and answer it is, frankly, ridiculous. Do you enjoy wasting our time? $\endgroup$ – David Richerby May 20 '15 at 7:30
  • 1
    $\begingroup$ Also, I don't think you need us to tell you that a Turing machine that moves its head to the right, and then moves its head back to the initial position has just moved its head to the left, violating your stated condition. $\endgroup$ – David Richerby May 20 '15 at 7:33
1
$\begingroup$

The usual answer would be that they are indeed much less powerful, somewhat like a finite state automaton, if I am not mistaken.

But there is a catch. Imagine a TM with two heads, one which is reading, another which is writing. Both only move right! If the reading head is always left of the writing head, the part of the tape in between can act as a queue, which makes the machine Turing complete.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.