Wang program

From Esolang

Wang programs were introduced by Wang [1] 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).

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.

[edit] 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 '+>').