1
$\begingroup$

My question is if the following statement is true or false:

Does every turing-recognized $B$ language has a turing machine $M$ that recognizes $B$ and fullfiles the following statement:

For every word $w$ the belongs to $B$, $w \in B$, the writing-reading head never moves to the left?

Notice that the condition is required only for words in the language. if $w \notin B$ then the head can move to the left as usual.

The statemet seems correct to me. I think I can simulate a regular $TM$ with this "special" $TM$, while saying that every time the head moves left, it will stay put. Couldn't prove it, though.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Can you construct a TM like that that accepts $a^nb^n$? $\endgroup$ – ratchet freak Jul 10 '18 at 9:41
  • 1
    $\begingroup$ Are working tapes available? $\endgroup$ – Andrej Bauer Jul 11 '18 at 8:00
2
$\begingroup$

False.

A Turing machine that can't move left can never write information on the tape, then go back to read it later. In other words, it can't store any information; it has no memory apart from its state.

This makes it into a finite state machine, which is significantly weaker than a Turing machine. (As ratchet freak points out in the comments, a finite state machine can't recognize the language $\{ 0^n 1^n | n \in \mathbb{N} \}$, while a Turing machine can.)

Note, however, that some Turing machines have multiple tapes. If you have another tape available, and can move left on that one, then there's no problem: just run once over the original tape and copy it onto your working tape, then run as normal, without ever moving the original head backward.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

If you only allow moving right (and no external memory), all your TM "knows" about the input already seen is the finite amount of information in its state. I.e., it can't do more than a finite state automaton.

|cite|improve this answer
$\endgroup$

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