P′′

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

Definition

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

Syntax

1. $R$ and $\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

Let a finite alphabet $𝒞=\{c_0\equiv ◻\}\cup \{c_1,c_2,\dots ,c_n\}$, with $n\ge 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 $c_0$. The machine has a single head that can read and write one square at a time and move along the tape.Template:SfnTemplate:Sfn

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

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 $\{0,1,\dots ,n\}$. All but finitely many squares initially contain the value $0$.

Instructions

Char.	Instruction
$R$	Shift the tape-head one square to the right (if possible). If the head is already at the right end of the tape, the instruction has no effect.
$\lambda$	Increment the current square modulo $(n+1)$, then shift the head one square to the left.
$($	Jump forward past $)$ if the current square = $0$
$)$	Jump backward past $($ if the current square $\ne 0$

Example words

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

Example 1

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

• $r\equiv \lambda R$

This snippet adds $1mod(n+1)$ to the current square.

• $r^{\prime }\equiv \{r{\}}^n\equiv \{\lambda R{\}}^n$

This snippet subtracts $1mod(n+1)$ from the current square.

• $L\equiv r^{\prime }\lambda \equiv \{\lambda R{\}}^n\lambda$

This macro shifts the head one square to the left.

Example 2

Based on these macro's, BöhmTemplate:Sfn gives the following word to compute the predecessor $(x-1)$ of an integer $x>0$:

$R(R)L(r^{\prime }(L(L))r^{\prime }L)Rr$

When P′′ is defined using square values in $\{0,1,\dots ,n\}$, the number $x$ is represented in bijective base-n notation $(d_1,\dots ,d_k{)}_{bijn}$, most significant digit first. These tuples appear in consecutive squares, flanked by $0$s, with the tape head on the leftmost $0$.

The expansion of the macro's depends on the modulus.

Modulus = 2, when tape squares take values in $\{0\equiv ◻,1\}$

When square values are in $\{0,1\}$, the word expands to

$R(R)\{\lambda R{\}}^1\lambda (\{\lambda R{\}}^1(\{\lambda R{\}}^1\lambda (\{\lambda R{\}}^1\lambda ))\{\lambda R{\}}^1\{\lambda R{\}}^1\lambda )R\lambda R$

that is

$R(R)\lambda R\lambda (\lambda R(\lambda R\lambda (\lambda R\lambda ))\lambda R\lambda R\lambda )R\lambda R$

In bijective base‑1 notation the number $8$ (for example) is encoded as $(1,1,1,1,1,1,1,1{)}_{bij1}$.
So the initial tape will be (with head position underlined)

$\phantom{|1}\cdots |\underset{\_}{0}|1|1|1|1|1|1|1|1|0\Vert$

After execution of the word the tape configuration is

$\phantom{|1}\cdots |0|\underset{\_}{0}|1|1|1|1|1|1|1|0\Vert$

, which corresponds to the bijective base‑1 encoding for 7.

Modulus = 3, when tape squares take values in $\{0,1,2\}$

When square values are in $\{0,1,2\}$, the word expands to

$R(R)\{\lambda R{\}}^2\lambda (\{\lambda R{\}}^2(\{\lambda R{\}}^2\lambda (\{\lambda R{\}}^2\lambda ))\{\lambda R{\}}^2\{\lambda R{\}}^2\lambda )R\lambda R$

that is

$R(R)\lambda R\lambda R\lambda (\lambda R\lambda R(\lambda R\lambda R\lambda (\lambda R\lambda R\lambda ))\lambda R\lambda R\lambda R\lambda R\lambda )R\lambda R$

In bijective base‑2 notation the number $8$ is encoded as $(1,1,2{)}_{bij2}$.
So the initial tape will be (with head position underlined)

$\phantom{|1}\cdots |\underset{\_}{0}|1|1|2|0\Vert$

After execution of the word the tape configuration is

$\cdots |0|\underset{\_}{0}|1|1|1|0\Vert$

, which corresponds to the bijective base‑2 encoding for 7.

Modulus = 256, when tape squares take values in $\{0,1,2,\cdots ,255\}$

When P′′ is defined with an alphabet of size $256,\mathrm{\Sigma }=\{0,1,\cdots ,255\}$, the word expands to

$R(R)\{\lambda R{\}}^{255}\lambda (\{\lambda R{\}}^{255}(\{\lambda R{\}}^{255}\lambda (\{\lambda R{\}}^{255}\lambda ))\{\lambda R{\}}^{255}\{\lambda R{\}}^{255}\lambda )R\lambda R$

Its full length is $3077$ characters.

In bijective base‑255 notation the number $35048731$ (for example) is encoded as $(2,29,1,1{)}_{bij255}$.
The initial tape will be (with head position underlined):

$\phantom{|0}\cdots |\underset{\_}{0}|2|29|1|1|0\Vert$

After execution of the word the tape configuration is

$\cdots |0|\underset{\_}{0}|2|28|255|255|0\Vert$

, which corresponds to the bijective base‑255 encoding for $35048730$.

Foundation of structured programming

Böhm proved that P′′ is Turing-complete: Template:Blockquote

The language demonstrates that programs can be written without using selection (if-then-else) constructs, only sequence and iteration are necessary. P′′ words are evaluated from left to right with backward control eliminated recursively. Böhm’s paper on the language P′′ is one of the earliest explicit statements of what we now call the single-entry single-exit (SESE) property: Template:Blockquote

This design anticipated Dijkstra's 1968 advocacy of structured programming.Template:Sfn While Dijkstra argued programmers should avoid goto statements,Template:Refn Böhm's P′′ prevented unstructured control flow through language design—enforcing structure at the source rather than requiring later transformation or programmer discipline.

His results were restated in the 1966 Böhm-Jacopini structured program theorem,Template:Sfn which combined Böhm's selection elimination with Jacopini's flowchart transformation method.

Relation to other programming languages

P′′ versus languages based on WHILE

In conventional high-level languages, a while loop executes a block of code based on a fixed boolean expression that is evaluated at the start of each iteration. The same condition is tested each time the loop executes:

while condition_expression:
    # loop body

In P′′, loops are written as $(q)$, where $q$ is a sequence of instructions. Loop continuation is determined dynamically by the tape head: after executing $q$, the program examines the value of the current tape square, which may change during execution because instructions in $q$ can move the head. This makes P′′ loops more general than conventional pre-test loops, as the loop condition is embedded in the data rather than specified separately. A conventional while loop is equivalent to a P′′ loop only when at ${(}^{\prime }$ and ${)}^{\prime }$ the head points to the same square.

Not every P′′ loop can be trivially transcribed to a standard while loop. For example, the word $(\lambda )$

• does nothing if the head scans initially $0$; otherwise
• goes to the left until it scans $0$, incrementing each square on its way.

This word cannot be translated to a while loop without rethinking the logic.

Relation to Brainfuck

In formal language theory, the language Brainfuck (hereafter: BF) may be regarded as a mirrored instantiation of P′′, where P′′ is defined with an alphabet of size $256,\mathrm{\Sigma }=\{0\equiv ◻,1,\cdots ,255\}$.

The two languages differ only in the orientation of their tapes: P′′ operates on a left-infinite tape, whereas BF operates on a right-infinite tape. As is standard for Turing-machine–like models, this difference can be eliminated by mirroring the tape and reversing the direction of head movement.

Under this convention, there exists a literal one-to-one correspondence between the instructions of P′′ and BF. Arithmetic operations and loop constructs are preserved directly, while head movements are reversed to account for the mirrored tape orientation. In other words, P′′ and BF are bisimilar under macro expansion with mirrored tapes/heads and disregarded input.

Instruction correspondence

#	P′′ pattern	BF pattern	Meaning
1	$\{\lambda R{\}}^{255}\lambda$	Template:Code	Composite pattern for head move
2	$\{\lambda R{\}}^{255}$	Template:Code	Arithmetic decrement ($mod256$)
3	$\lambda R$	Template:Code	Arithmetic increment ($mod256$)
4	$\lambda$	Template:Code	Arithmetic increment plus head move
5	$R$	Template:Code	Head move
6	$($	Template:Code	Loop start
7	$)$	Template:Code	Loop end

The correspondences between P′′ and BF can be interpreted as (nondeterministic) bidirectional term-rewrite rules.
For example, the BF program Template:Code can be translated to P′′ in two ways: Template:Olist

Note that the tape heads in P′′ and BF move in opposite directions.

Tape mirroring

Execution of the translated program requires a mirrored tape configuration. The left-infinite tape on which P′′ operates

$\cdots |A|B|C|\underset{\_}{D}|E|F|G\Vert$

must be mirrored to a right-infinite tape on which BF operates

$\Vert G|F|E|\underset{\_}{D}|C|B|A\cdots$

The BF head is initialized at the position corresponding to the P′′ head under mirroring. With this arrangement, execution of a BF program related by the instruction correspondence mimics the behavior of the corresponding P′′ program.

Loosely speaking, P′′ — when defined with an alphabet of size 256 — can be translated into BF by

1. replacing every occurrence of $\lambda$ with Template:Code, and then, in the resulting program,
2. reversing the direction of all pointer-movement instructions Template:Code and Template:Code.

Example translation from P′′ to BF

Consider the P′′ program from example 2 above:

$R(R)\{\lambda R{\}}^{255}\lambda (\{\lambda R{\}}^{255}(\{\lambda R{\}}^{255}\lambda (\{\lambda R{\}}^{255}\lambda ))\{\lambda R{\}}^{255}\{\lambda R{\}}^{255}\lambda )R\lambda R$

that is

$R(R)\lambda R\lambda R\lambda R\cdots \cdots \cdots R\lambda R$

The tape

• P′′ starts computations on a populated tape, with a given head position.
• BF starts computations on an empty tape, with the head pointing to the lefmost cell.

So the translated BF program first has to up its tape to the mirrored copy of the tape on which the P′′ program started.

In bijective base‑255 notation the number $35048731$ is encoded as $(2,29,1,1{)}_{bij255}$.
In P′′, an initial tape can be (with head position underlined):

$\cdots |\underset{\_}{0}|2|29|1|1|0\Vert$

In BF, the mirrored tape

$\Vert 0|1|1|29|2|\underset{\_}{0}|\cdots$

can be input by the code

                                // Cell 0 = 0
>+                              // Cell 1 = 1
>+                              // Cell 2 = 1
>+++++++++++++++++++++++++++++  // Cell 3 = 29
>++                             // Cell 4 = 2
>                               // Head initially on cell 5

The execution of a program translated to BF will transform the mirrored tape to the final state

$\Vert 0|255|255|28|2|\underset{\_}{0}|0|\cdots$

which corresponds to the bijective base‑255 encoding for $35048730$.

The program
The correspondences 1, 2, 3 in the table above are optimizing rules that correspond to the macro's L, r' and r given by Böhm.Template:Sfn Using these shortcuts the shortest translation to BF has 18 instructions (+ the initialization of the tape):

<[<]>[-[>[>]]->]<+

When no shortcut is applied, the shortest translation by the rules has 4612 instructions, not including instructions required to initialize the tape.

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

See also

• Structured program theorem

Notes and references

Notes

References

Bibliography

• Template:Cite journal

• Template:Cite journal

• Template:Cite journal Republished in Template:Harvnb

• Template:Cite journal

• Template:Cite web

• Template:Cite web

• Template:Cite book

External links

• Template:Cite web

• Template:Cite web: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.

• Template:Cite web