4
$\begingroup$

A Wang B-machine is Turing-complete and has only 4 instructions:

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

Inspired by P′′, consider a machine with the following instructions:

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

Note that mark = markleft; right. What is the computational class of this machine?

$\endgroup$
2
  • 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, 2017 at 11:55
  • $\begingroup$ @orlp I edited the question to ask for the computational class. $\endgroup$
    – user76284
    Jun 23, 2022 at 18:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.