P′′ Explained

P′′
Released:	1964
Typing:	untyped
Influenced:	Brainfuck

P′′ (P double prime^[1]) is a primitive computer programming language created by Corrado Böhm^{[2] [3]} in 1964 to describe a family of Turing machines.

Definition

$\backslash mathcal^$ (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet $\backslash$, as follows:

Syntax

1. $R$ and $\backslash lambda$ are words in P′′.
2. If $q\_1$ and $q\_2$ are words in P′′, then $q\_1\; q\_2$ is a word in P′′.
3. If $q$ is a word in P′′, then $(q)$ is a word in P′′.
4. Only words derivable from the previous three rules are words in P′′.

Semantics

• $\backslash$ is the tape-alphabet of a Turing machine with left-infinite tape, $\backslash 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.
• $\backslash alpha$ is a predicate saying that the current symbol is not $\backslash 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).
• $\backslash lambda$ means replace the current symbol $c\_i$ with $c\_$, and then move the tape-head leftward one cell.
• $q\_1\; q\_2$ means the function composition $q\_2\; \backslash 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 $\backslash 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^\backslash prime,\; L,\; R$ where $r\; \backslash equiv\; \backslash lambda\; R,\; r^\backslash prime\; \backslash equiv\; r^n$ with $r^n$ denoting the $n$th iterate of $r$, and $L\; \backslash equiv\; r^\backslash prime\; \backslash lambda$. These are the equivalents of the six respective Brainfuck commands,,,,, . Note that since $c\_\; \backslash equiv\; c\_0\; \backslash equiv\; \backslash 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^\backslash 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\; \backslash ldots,\; c\_k$ encoding the digits $1,\; 2,\; \backslash ldots,\; k$ respectively, and to have $\backslash Box$ before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as $\backslash Box\; c\_1\; c\_1\; c\_2\; \backslash Box$, because 8 in base-2 is 100, reverse the digits, and add one to each of them.) At the beginning and end of the computation, the tape-head is on the $\backslash Box$ preceding the digit-string.

External links

• P′′Online interpreter: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.

Notes and References

1. Web site: PDBL: A tool for Turing machine simulation. 4 September 2021.
2. Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
3. 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.)