Wang program

Wang programs were introduced by Wang in what he called a "program formulation" of Turing machines. For a Turing machine with binary tape-alphabet, a Wang program replaces the state-transition function with a program based on the instruction-set M, E, L, R, Ck (meaning, respectively, Mark, Erase, move Left, move Right, and Conditionally jump to the instruction labelled k if the current cell is marked).

Wang B-machine is the above except that the Erase instruction is omitted; it is still Turing-complete.

The Wang program concept generalises to a tape-alphabet of size m >= 2 by using the instruction-set Wi, L, R, Ck, where Wi writes the i-th letter of the alphabet into the current tape-cell.

Similar computational models

A Brainfuck-like computational model results from Wang's model if

• labels and conditional jump instructions are replaced by matching brackets '[', ']', and
• a cyclic ordering is applied to the tape-alphabet, with write instructions replaced by '+' and '-', understood as instructions to change the current letter to the next and previous letter (respectively) in the cyclic ordering.

The Fm languages are then obtained by also removing '-' from the instruction-set. Bohm's programming language P'' for TMs with a left-infinite tape results if the instructions '+' and '<' are then combined into one instruction equivalent to '+<' (or, for a right-infinite tape, by combining '+' and '>' into '+>').

Sequential Tag System/Cyclic Tag System to brainfuck to B-machine

In the article Brainfuck minus - is represented a way to translate Sequential Tag System and Cyclic Tag System to brainfuck, and then from brainfuck to B-machine.

Computational class

The Wang program formulation of Turing machines is Turing-complete by construction.

See also

• Fm