4
$\begingroup$

A Wang B-machine has only 4 instructions:

  • right: Move tape head right
  • left: Move tape head left
  • mark: Mark square under tape head
  • branch: If square under tape head is marked, jump to instruction $n$.

Is the following instruction set also Turing-complete?

  • right: Move tape head right
  • markleft: Mark square under tape head, then move tape head left
  • branch: If square under tape head is marked, jump to instruction $n$.

    I know that mark = right ∘ markleft, but left cannot be expressed so easily. The P'' language is an example of a language that achieves Turing completeness with a combined mark-move instruction.

$\endgroup$
  • 2
    $\begingroup$ I highly doubt it. Because you can't move left without destroying its contents (marking everything), effectively the tape has become read-once memory. Since the only other information (the instruction pointer) is finite, I believe you become limited to something similar to a pushdown automata. $\endgroup$ – orlp May 13 '17 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.