# P′′

P′′ (P double prime) is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines.

## Definition

P$^{′′}${\textstyle {\mathcal {P}}^{\prime \prime }} (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet {R, λ, (, )}{\textstyle \{R, \lambda , (, )\}}, as follows:

### Syntax

* R{\textstyle R} and λ{\textstyle \lambda } are words in P′′.
* If q$_1${\textstyle q_{1}} and q$_2${\textstyle q_{2}} are words in P′′, then q$_1$q$_2${\textstyle q_{1}q_{2}} is a word in P′′.
* If q{\textstyle q} is a word in P′′, then (q){\textstyle (q)} is a word in P′′.
* Only words derivable from the previous three rules are words in P′′.

### Semantics

* {◻, c$_1$, c$_2$, …, c$_n$}{\textstyle \{\Box , c_{1}, c_{2}, \ldots , c_{n}\}} is the tape-alphabet of a Turing machine with left-infinite tape, ◻{\textstyle \Box } being the blank symbol, equivalent to c$_0${\textstyle c_{0}}.
* All instructions in P′′ are permutations of the set X{\textstyle 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.
* α{\textstyle \alpha } is a predicate saying that the current symbol is not ◻{\textstyle \Box }. It is not an instruction and is not used in programs, but is instead used to help define the language.
* R{\textstyle R} means move the tape-head rightward one cell (if possible).
* λ{\textstyle \lambda } means replace the current symbol c$_i${\textstyle c_{i}} with c$_{(i+1)mod(n+1)}${\textstyle c_{(i+1){\bmod {}n+1)}}, and then move the tape-head leftward one cell.
* q$_1$q$_2${\textstyle q_{1}q_{2}} means the function composition q$_2$∘q$_1${\textstyle q_{2}\circ q_{1}}. In other words, the instruction q$_1${\textstyle q_{1}} is performed before q$_2${\textstyle q_{2}}.
* (q){\textstyle (q)} means iterate q{\textstyle q} in a while loop, with the condition α{\textstyle \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 ({\textstyle, ){\textstyle )} and the four words r, r$^′$, L, R{\textstyle r, r^{\prime }, L, R} where r≡λR, r$^′$≡r$^n${\textstyle r\equiv \lambda R, r^{\prime }\equiv r^{n}} with r$^n${\textstyle r^{n}} denoting the n{\textstyle n}th iterate of r{\textstyle r}, and L≡r$^′$λ{\textstyle L\equiv r^{\prime }\lambda }. These are the equivalents of the six respective Brainfuck commands [, ], +, -, <, >. Note that since c$_{n+1}$≡c$_0$≡◻{\textstyle c_{n+1}\equiv c_{0}\equiv \Box }, incrementing the current symbol n{\textstyle n} times will wrap around so that the result is to "decrement" the symbol in the current cell by one (r$^′${\textstyle 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$…, c$_k${\textstyle c_{1}, c_{2}\ldots , c_{k}} encoding the digits 1, 2, …, k{\textstyle 1, 2, \ldots , k} respectively, and to have ◻{\textstyle \Box } before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as ◻c$_1$c$_1$c$_1$c$_2$◻{\textstyle \Box c_{1}c_{1}c_{1}c_{2}\Box }, because 8 in base-2 is 1000, reverse the digits, and add one to each of them.) At the beginning and end of the computation, the tape-head is on the ◻{\textstyle \Box } preceding the digit-string.