P′′ (P double prime) is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines. It provided one of the earliest formulations of the single-entry single-exit principle central to structured programming.

P′′ is formally defined as a set of words on the four-instruction alphabet ${\displaystyle \{\,R,\lambda ,(,)\,\}}$, as follows:

Let a finite alphabet ${\displaystyle {\mathcal {C}}=\{c_{0}\equiv \Box \}\cup \{c_{1},c_{2},\dots ,c_{n}\}}$, with ${\displaystyle n\geq 1}$, be given, together with a Turing Machine equipped with a tape that is infinite to the left and divided into squares, only finitely many of which initially contain non-blank symbols. The remaining squares contain the blank symbol ${\displaystyle c_{0}}$. The machine has a single head that can read and write one square at a time and move along the tape.

For formalization, the alphabet symbols ${\displaystyle c_{i}}$ are identified with their indices ${\displaystyle i}$. The integer ${\displaystyle 0}$ corresponds to the blank symbol (${\displaystyle \Box }$). Arithmetic on squares is performed modulo ${\displaystyle (n+1)}$, so incrementing ${\displaystyle n}$ produces ${\displaystyle 0}$ and decrementing ${\displaystyle 0}$ produces ${\displaystyle n}$. This formulation matches Böhm’s definition and differs only in notation, replacing symbolic alphabet elements with their numerical indices.

A program (called: "word") operates on a tape configuration consisting of a given initial tape together with the position of the head. Each tape square contains a value from the set ${\displaystyle \{0,1,\dots ,n\}}$. All but finitely many squares initially contain the value ${\displaystyle 0}$.

Instructions

Define ${\displaystyle \{H\}^{k}\;\rightarrow \;\underbrace {HH\dots H} _{k{\text{ times}}}}$ as repeated application of an instruction sequence. For example, ${\displaystyle \{\lambda R\}^{3}\;\rightarrow \;\lambda R\,\lambda R\,\lambda R}$.

Böhm defines three macro's r, r' and L: