Wang B-machine
Encyclopedia
As presented by Hao Wang (1954, 1957), his basic machine B is an extremely simple computational model equivalent to the Turing machine
. It is "the first formulation of a Turing-machine theory in terms of computer-like models" (Minsky (1967) p. 200). With only 4 sequential instructions it is very similar to, but even simpler than, the 7 sequential instructions of the Post-Turing machine
. In the same paper, Wang introduced a variety of equivalent machines, including what he called the W-machine, which is the B-machine with an "erase" instruction added to the instruction set.
A sample of a simple B-machine instruction is his example (p. 65):
He rewrites this as a collection of ordered pairs:
Wang's W-machine is simply the B-machine with the one additional instruction
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
. It is "the first formulation of a Turing-machine theory in terms of computer-like models" (Minsky (1967) p. 200). With only 4 sequential instructions it is very similar to, but even simpler than, the 7 sequential instructions of the Post-Turing machine
Post-Turing machine
A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a...
. In the same paper, Wang introduced a variety of equivalent machines, including what he called the W-machine, which is the B-machine with an "erase" instruction added to the instruction set.
Description
As defined by Wang (1954) the B-machine has at its command only 4 instructions:- (1) → : Move tape-scanning head one tape square to the right (or move tape one square left), then continue to next instruction in numerical sequence;
- (2) ← : Move tape-scanning head one tape square to the left (or move tape one square right), then continue to next instruction in numerical sequence;
- (3) * : In scanned tape-square print mark * then go to next instruction in numerical sequence;
- (4) Cn: Conditional "transfer" (jump, branch) to instruction "n": If scanned tape-square is marked then go to instruction "n" else (if scanned square is blank) continue to next instruction in numerical sequence.
A sample of a simple B-machine instruction is his example (p. 65):
- 1. *, 2. →, 3. C2, 4. →, 5. ←
He rewrites this as a collection of ordered pairs:
- { ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }
Wang's W-machine is simply the B-machine with the one additional instruction
- (5) E : In scanned tape-square erase the mark * (if there is one) then go to next instruction in numerical sequence.