# Is a reduced Wang B-machine Turing-complete?

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.

• 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. – orlp May 13 '17 at 11:55