P′′

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

## Contents

* 1 Definition
* 1.1 Syntax
* 1.2 Semantics
* 2 Example words
* 2.1 Example 1
* 2.2 Example 2
* 3 Foundation of structured programming
* 4 Relation to other programming languages
* 4.1 P′′ versus languages based on WHILE
* 4.2 Relation to Brainfuck
* 4.2.1 Instruction correspondence
* 4.2.2 Tape mirroring
* 4.2.3 Example translation from P′′ to BF
* 5 See also
* 6 Notes and references
* 7 Bibliography
* 8 External links

## Definition

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

### Syntax

1. R and λ are words in P′′.
2. If q1 and q2 are words in P′′, then q1q2 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 𝒞={c0≡◻}∪{c1,c2,…,cn}, with n≥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 c0. The machine has a single head that can read and write one square at a time and move along the tape.[4][5]

For formalization, the alphabet symbols ci 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.[n 2]

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,…,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.
λ | Increment the current square modulo (n+1),[n 3] then shift the head one square to the left.
( | Jump forward past ) if the current square = 0 [n 4]
) | Jump backward past ( if the current square ≠0 [n 4]

## Example words

Define {H}k->HH…H⏟k times as repeated application of an instruction sequence.[n 5] For example, {λR}3->λRλRλR.

### Example 1

Böhm defines three macro's `r`, `r'` and `L`:[6]

* r≡λR

This snippet adds 1mod(n+1) to the current square.[n 3]

* r′≡{r}n≡{λR}n

This snippet subtracts 1mod(n+1) from the current square.[n 6]

* L≡r′λ≡{λR}nλ

This macro shifts the head one square to the left.

### Example 2

Based on these macro's, Böhm[2] gives the following word to compute the predecessor (x−1) of an integer x>0: R(R)L(r′(L(L))r′L)Rr

When P′′ is defined using square values in {0,1,…,n}, the number x is represented in bijective base-n notation (d1,…,dk)bijn, most significant digit first. These tuples appear in consecutive squares, flanked by 0s, 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≡◻,1}

When square values are in {0,1}, the word expands to R(R){λR}1λ({λR}1({λR}1λ({λR}1λ)){λR}1{λR}1λ)RλR that is R(R)λRλ(λR(λRλ(λRλ))λRλRλ)RλR

In bijective base‑1 notation the number 8 (for example) is encoded as (1,1,1,1,1,1,1,1)bij1.[n 7]
So the initial tape will be (with head position underlined) |1⋯|0_|1|1|1|1|1|1|1|1|0‖

After execution of the word the tape configuration is |1⋯|0|0_|1|1|1|1|1|1|1|0‖

, which corresponds to the bijective base‑1 encoding for 7.[n 8]

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){λR}2λ({λR}2({λR}2λ({λR}2λ)){λR}2{λR}2λ)RλR that is R(R)λRλRλ(λRλR(λRλRλ(λRλRλ))λRλRλRλRλ)RλR

In bijective base‑2 notation the number 8 is encoded as (1,1,2)bij2.[n 9]
So the initial tape will be (with head position underlined) |1⋯|0_|1|1|2|0‖

After execution of the word the tape configuration is ⋯|0|0_|1|1|1|0‖

, which corresponds to the bijective base‑2 encoding for 7.[n 10]

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

When P′′ is defined with an alphabet of size 256,Σ={0,1,⋯,255}, the word expands to R(R){λR}255λ({λR}255({λR}255λ({λR}255λ)){λR}255{λR}255λ)RλR Its full length is 3077 characters.[n 11]

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

|0⋯|0_|2|29|1|1|0‖

After execution of the word the tape configuration is ⋯|0|0_|2|28|255|255|0‖

, which corresponds to the bijective base‑255 encoding for 35048730.[n 13]

## Foundation of structured programming

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

> For every partial recursive function

> 𝕗

> of

> m≥0

> variables a programme

> Pj∈𝒫′′

> exists which computes it.

— Böhm (1964)[7]

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:

> a) It is only possible to enter a cycle from its first instruction, ...
> b) It is only possible to exit a cycle from its last instruction.

— Böhm (1964)[8]

This design anticipated Dijkstra's 1968 advocacy of structured programming.[9] While Dijkstra argued programmers should avoid goto statements,[n 14] 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,[3] 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 while 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 (′ and )′ the head points to the same square.

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

* does nothing if the head scans initially 0; otherwise
* goes to the left until it scans the first 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,Σ={0≡◻,1,⋯,255}.[n 15]

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.[n 16] 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 | {λR}255λ[n 5] | > | Composite pattern for head move
2 | {λR}255[n 5] | − | Arithmetic decrement (mod256)
3 | λR | + | Arithmetic increment (mod256)
4 | λ | +> | Arithmetic increment plus head move
5 | R | < | Head move
6 | ( | [ | Loop start
7 | ) | ] | Loop end

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

(i) | λ | , by applying rule 4,

|
|

(ii) | λR{λR}255λ | , by applying rules 3 and 1.

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 ⋯|A|B|C|D_|E|F|G‖

must be mirrored to a right-infinite tape on which BF operates ‖G|F|E|D_|C|B|A⋯

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 `λ` with `+<`, and then, in the resulting program,
2. reversing the direction of all pointer-movement instructions `<` and `>`.

#### Example translation from P′′ to BF

Consider the P′′ program from example 2 above: R(R){λR}255λ({λR}255({λR}255λ({λR}255λ)){λR}255{λR}255λ)RλR that is R(R)λRλRλR⋯⋯⋯Rλ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.[n 12]
In P′′, an initial tape can be (with head position underlined): ⋯|0_|2|29|1|1|0‖

In BF, the mirrored tape ‖0|1|1|29|2|0_|⋯

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

‖0|255|255|28|2|0_|0|⋯

which corresponds to the bijective base‑255 encoding for 35048730.[n 13]

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.[6] 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

1. ↑ They may for instance be mapped to a 256-value byte-oriented character encoding (e.g. extended ASCII), as in Brainfuck (see below).
2. ↑ The numeric values may be mapped to the symbols c0,c1,…,cn via a fixed lookup table.[n 1] These labels serve only as tags for interpretation and play no role in the execution of the program itself.
3. ↑ 3.0 3.1 In particular, if i=n, the next value is 0 (wrap-around).
4. ↑ 4.0 4.1 Böhm defines a unary predicate — p in (Böhm 1964), α in (Böhm Jacopini) — that is true iff the square actually scanned (by the Turing machine head) is blank (i.e. contains ◻).
5. ↑ 5.0 5.1 5.2 In the context of P′′, repetition could equivalently be written using bracket notation [⋅]k, as in (Böhm 1964). However, since square brackets already denote the repetition (loop) operator in Brainfuck, we instead use braces {⋅}k to indicate repetition of an instruction sequence and avoid notational ambiguity.
6. ↑ In particular, if i=0, the next value is n (wrap-around).
7. ↑ 8=1⋅17+1⋅16+1⋅15+1⋅14+1⋅13+1⋅12+1⋅11+1⋅10.
8. ↑ 7=1⋅16+1⋅15+1⋅14+1⋅13+1⋅12+1⋅11+1⋅10.
9. ↑ 8=1⋅22+1⋅21+2⋅20.
10. ↑ 7=1⋅22+1⋅21+1⋅20.
11. ↑ 3077=4+510+2+510+1+510+2+510+3+510+510+5.
12. ↑ 12.0 12.1 35048731=2⋅2553+29⋅2552+1⋅2551+1⋅2550.
13. ↑ 13.0 13.1 35048730=2⋅2553+28⋅2552+255⋅2551+255⋅2550.
14. ↑ (Dijkstra 1968): "The unbridled use of the go to statement has as an immediate consequence that it becomes terribly hard to find a meaningful set of coordinates in which to describe the process progress. ... The go to statement as it stands is just too primitive, it is too much an invitation to make a mess of one's program."
15. ↑ (Esolang 2026): "In publishing the formal programming language P′′ in 1964, Corrado Böhm used six symbols precisely equivalent to the brainfuck commands `+`, `-`, `<`, `>`, `[`, and `]`, and provided an explicit program for each of the basic functions that together serve to compute any partial recursive function. (So in a very real sense, the first "brainfuck" programs appear in Bohm's 1964 paper.)"
16. ↑ This correspondence relies only on a reversal of tape orientation, a standard equivalence for Turing-machine–like computational models. No modification of BF semantics is required. Under this interpretation, BF serves as a concrete realization of the abstract P′′ machine up to tape reversal.

References

1. ↑ GitHub 2021.
2. ↑ 2.0 2.1 Böhm 1964.
3. ↑ 3.0 3.1 Böhm & Jacopini 1966.
4. ↑ Böhm 1964, p. 185.
5. ↑ Böhm & Jacopini 1966, p. 370.
6. ↑ 6.0 6.1 Böhm 1964, pp. 190, 190, 187 (footnote).
7. ↑ Böhm 1964, p. 191, Main result of this paper.
8. ↑ Böhm 1964, p. 189.
9. ↑ Dijkstra 1968.

## Bibliography

* Böhm, Corrado (June 1962). "Macchine a indirizzi, dotate di un numero minimo di istruzioni" (in it). Rendiconti dell’Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali, Serie VIII 32: 923–930. https://www.bdim.eu/item?id=RLINA_1962_8_32_6_923_0.

* Böhm, Corrado (1964). "On a family of Turing machines and the related programming language". ICC Bulletin 3: 185–194. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/36B0D3C5B690EB7BD0A30C079CC2DC8E/S0022481200068638a.pdf/corrado-bohm-on-a-family-of-turing-machines-and-the-related-programming-language-icc-bulletin-vol-3-1964-pp-185194.pdf.

* Böhm, Corrado; Jacopini, Giuseppe (May 1966). "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules". Communications of the ACM 9 (5): 366–371. doi:10.1145/355592.365646. Republished in Yourdon 1979, pp. 13–25

* Dijkstra, Edsger (March 1968). "Go To Statement Considered Harmful". Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947.

* Esolang, Wiki (2026). "Brainfuck". https://esolangs.org/wiki/Brainfuck.

* GitHub (2021-09-04). "PDBL: A tool for Turing machine simulation". https://github.com/Pbtflakes/pdbl.

* Yourdon, E. N., ed (1979). Classics in Software Engineering. New York, NY: Yourdon Press. pp. xi, 424. ISBN 978-0-917072-14-7.

## External links

* Barendregt, Henk (2019-11-06). "Gems of Corrado Böhm". Radboud University Nijmegen. https://www.cs.ru.nl/~henk/CBM.pdf.

* Elsner, Mathias. "Esoteric Programming Languages — P′′ in ›Production Mode‹". http://www.mathiaselsner.de/esolangs/EN/P_dblp_99btls.html. : Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.

* Esolangs Wiki. "P′′". https://esolangs.org/wiki/P''.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/P′′. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=P′′&oldid=4297289"