P′′ (P double prime) is a primitive computer programming language created by Corrado BöhmBöhm, C.: "On a family of Turing machines and the related programming language", ICC Bull.
3, 185-194, July 1964.Bö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.) in 1964 to describe a family of Turing machines.
Definition
\mathcal{P}^{\prime\prime} (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet \{R, \lambda, (, )\}, as follows: Syntax
R and \lambda are words in P′′.
If q_1 and q_2 are words in P′′, then q_1 q_2 is a word in P′′.
If q is a word in P′′, then (q) is a word in P′′.
Only words derivable from the previous three rules are words in P′′.
Semantics
\{\Box, c_1, c_2, \ldots, c_n\} is the tape-alphabet of a Turing machine with left-infinite tape, \Box being the blank symbol, equivalent to c_0.
All instructions in P′′ are permutations of the set X of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head.
\alpha is a predicate saying that the current symbol is not \Box.
It is not an instruction and is not used in programs, but is instead used to help define the language.
R means move the tape-head rightward one cell (if possible).
\lambda means replace the current symbol c_i with c_{(i+1) \bmod (n+1)}, and then move the tape-head leftward one cell.
q_1 q_2 means the function composition q_2 \circ q_1.
In other words, the instruction q_1 is performed before q_2.
(q) means iterate q in a while loop, with the condition \alpha.
Relation to other programming languages
P′′ was the first "GOTO-less" imperative structured programming language to be proven Turing-complete
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 r, r^\prime, L, R where r \equiv \lambda R, r^\prime \equiv r^n with r^n denoting the nth iterate of r, and L \equiv r^\prime \lambda.
These are the equivalents of the six respective Brainfuck commands .
Note that since c_{n+1} \equiv c_0 \equiv \Box, incrementing the current symbol n times will wrap around so that the result is to "decrement" the symbol in the current cell by one (r^\prime).
Example program
Böhm gives the following program to compute the predecessor (x-1) of an integer x > 0:
R(R)L(r^\prime(L(L))r^\prime L)Rr
which translates directly to the equivalent Brainfuck program:
>[>]<[−[<[<]]−<]>+
The program expects an integer to be represented in bijective base-k notation, with c_1, c_2 \ldots, c_k encoding the digits 1, 2, \ldots, k respectively, and to have \Box before and after the digit-string.
(E.g., in bijective base-2, the number eight would be encoded as \Box c_1 c_1 c_2 \Box, because 8 in bijective base-2 is 112.)
At the beginning and end of the computation, the tape-head is on the \Box preceding the digit-string.
References
Weblinks
P′′Online interpreter: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.
