P′′

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.

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

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

• ${\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 ${\textstyle c_{0}}$.
• All instructions in P′′ are permutations of the set ${\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.
• ${\textstyle R}$ means move the tape-head rightward one cell (if possible).
• ${\textstyle \lambda }$ means replace the current symbol ${\textstyle c_{i}}$ with ${\textstyle c_{(i+1){\bmod {(}}n+1)}}$, and then move the tape-head leftward one cell.
• ${\textstyle q_{1}q_{2}}$ means the function composition ${\textstyle q_{2}\circ q_{1}}$. In other words, the instruction ${\textstyle q_{1}}$ is performed before ${\textstyle q_{2}}$.
• ${\textstyle (q)}$ means iterate ${\textstyle q}$ in a while loop, with the condition ${\textstyle \alpha }$.

• P′′ was the first "GOTO-less" imperative structured programming language to be proven Turing-complete^[2][4]
• 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 ${\textstyle r,r^{\prime },L,R}$ where ${\textstyle r\equiv \lambda R,r^{\prime }\equiv r^{n}}$ with ${\textstyle r^{n}}$ denoting the ${\textstyle n}$-th iterate of ${\textstyle r}$, and ${\textstyle L\equiv r^{\prime }\lambda }$. These are the equivalents of the six respective Brainfuck commands [, ], +, -, <, >. Note that since ${\textstyle c_{n+1}\equiv c_{0}\equiv \Box }$, incrementing the current symbol ${\textstyle n}$ times will wrap around so that the result is to "decrement" the symbol in the current cell by one (${\textstyle r^{\prime }}$).

Böhm^[2] gives the following program to compute the predecessor ${\displaystyle (x-1)}$ of an integer ${\displaystyle x>0}$:^[5] $${\displaystyle R(R)L(r^{\prime }(L(L))r^{\prime }L)Rr}$$ where ${\displaystyle \;r\equiv \lambda R,\quad r'\equiv r^{n}}$(the ${\displaystyle n}$-th iterate of ${\displaystyle r}$),${\displaystyle \quad L\equiv r^{\prime }\lambda }$

The program expects an integer to be represented in bijective base-k notation, with ${\textstyle c_{1},c_{2},\ldots ,c_{k}}$ encoding the digits ${\textstyle 1,2,\ldots ,k}$ respectively, and to have ${\displaystyle \Box }$ before and after the digit‑string. (E.g. in bijective base‑2 the number eight would be encoded as ${\textstyle \Box \,c_{1}\,c_{1}\,c_{2}\,\Box }$, as ${\textstyle 8=1\cdot 2^{2}+1\cdot 2^{1}+2\cdot 2^{0}}$.) At the beginning and end of the computation, the tape‑head is on the ${\displaystyle \Box }$ preceding the digit‑string. The output is ${\textstyle \Box \,c_{1}\,c_{1}\,c_{1}\,\Box }$, the bijective base‑2 encoding for 7. Here, ${\displaystyle n=2}$.

This example translates directly to the equivalent Brainfuck program:

>[>]<[−[<[<]]−<]>+

• Barendregt, Henk (6 November 2019). "Gems of Corrado Böhm" (PDF). Radboud University Nijmegen. Retrieved 6 December 2025.

• Elsner, Mathias. "Esoteric Programming Languages — P′′ in ›Production Mode‹". www.mathiaselsner.de. Retrieved 6 December 2025.: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.

• Esolangs Wiki. "P′′". Esolangs. Retrieved 6 December 2025.