(hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet , as follows:
Syntax
and are words in P′′.
If and are words in P′′, then is a word in P′′.
If is a word in P′′, then is a word in P′′.
Only words derivable from the previous three rules are words in P′′.
Semantics
is the tape-alphabet of a
Turing machine with left-infinite tape, being the blank symbol, equivalent to .
All instructions in P′′ are
permutations of the set of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head.
is a
predicate saying that the current symbol is not . It is not an instruction and is not used in programs, but is instead used to help define the language.
means move the tape-head rightward one cell (if possible).
means replace the current symbol with , and then move the tape-head leftward one cell.
means the
function composition. In other words, the instruction is performed before .
means iterate in a
while loop, with the condition .
The
Brainfuck language (apart from its I/O commands) is a minor informal variation of P′′. Böhm gives explicit P′′ programs for each of a set of basic functions sufficient to compute any
computable function, using only , and the four words where with denoting the th
iterate of , and . These are the equivalents of the six respective Brainfuck commands , , +, -, <, >. Note that since , incrementing the current symbol times will wrap around so that the result is to "decrement" the symbol in the current cell by one ().
Example program
Böhm[2] gives the following program to compute the predecessor (x-1) of an integer x > 0:
which translates directly to the equivalent
Brainfuck program:
>><−<<]]−<>+
The program expects an integer to be represented in bijective base-k notation, with encoding the digits respectively, and to have before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as , because 8 in bijective base-2 is 112.) At the beginning and end of the computation, the tape-head is on the preceding the digit-string.
^
abcBöhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
^
abBöhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the
structured program theorem.)
(hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet , as follows:
Syntax
and are words in P′′.
If and are words in P′′, then is a word in P′′.
If is a word in P′′, then is a word in P′′.
Only words derivable from the previous three rules are words in P′′.
Semantics
is the tape-alphabet of a
Turing machine with left-infinite tape, being the blank symbol, equivalent to .
All instructions in P′′ are
permutations of the set of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head.
is a
predicate saying that the current symbol is not . It is not an instruction and is not used in programs, but is instead used to help define the language.
means move the tape-head rightward one cell (if possible).
means replace the current symbol with , and then move the tape-head leftward one cell.
means the
function composition. In other words, the instruction is performed before .
means iterate in a
while loop, with the condition .
The
Brainfuck language (apart from its I/O commands) is a minor informal variation of P′′. Böhm gives explicit P′′ programs for each of a set of basic functions sufficient to compute any
computable function, using only , and the four words where with denoting the th
iterate of , and . These are the equivalents of the six respective Brainfuck commands , , +, -, <, >. Note that since , incrementing the current symbol times will wrap around so that the result is to "decrement" the symbol in the current cell by one ().
Example program
Böhm[2] gives the following program to compute the predecessor (x-1) of an integer x > 0:
which translates directly to the equivalent
Brainfuck program:
>><−<<]]−<>+
The program expects an integer to be represented in bijective base-k notation, with encoding the digits respectively, and to have before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as , because 8 in bijective base-2 is 112.) At the beginning and end of the computation, the tape-head is on the preceding the digit-string.
^
abcBöhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
^
abBöhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the
structured program theorem.)