P′′

P′′
Paradigm	Imperative, structured
Designed by	Corrado Böhm
First appeared	1964
Typing discipline	untyped
Website	{{#property:P856}}
Dialects
Brainfuck
Influenced
Brainfuck

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

${𝒫}^{\prime \prime }$ (hereinafter written 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

• $\{◻,c_1,c_2,\dots ,c_n\}$ is the tape-alphabet of a Turing machine with left-infinite tape, $◻$ being the blank symbol, equivalent to $c_0$.
• All instructions in P′′ are permutations of the set $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.
• $\alpha$ is a predicate saying that the current symbol is not $◻$. It is not an instruction and is not used in programs, but is instead used to help define the language.
• $R$ means move the tape-head rightward one cell (if possible).
• $\lambda$ means replace the current symbol $c_i$ with $c_{(i+1)mod(n+1)}$, and then move the tape-head leftward one cell.
• $q_1{q}_2$ means the function composition $q_2\circ q_1$. In other words, the instruction $q_1$ is performed before $q_2$.
• $(q)$ means iterate $q$ in a while loop, with the condition $\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 $($, $)$ and the four words $r,r^{\prime },L,R$ where $r\equiv \lambda R,r^{\prime }\equiv r^n$ with $r^n$ denoting the $n$-th iterate of $r$, and $L\equiv r^{\prime }\lambda$. These are the equivalents of the six respective Brainfuck commands [, ], +, -, <, >. Note that since $c_{n+1}\equiv c_0\equiv ◻$, incrementing the current symbol $n$ times will wrap around so that the result is to "decrement" the symbol in the current cell by one ($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$$ where $r\equiv \lambda R,r^{\prime }\equiv r^n$(the $n$-th iterate of $r$),$L\equiv r^{\prime }\lambda$

The program expects an integer to be represented in bijective base-k notation, with $c_1,c_2,\dots ,c_k$ encoding the digits $1,2,\dots ,k$ respectively, and to have $◻$ before and after the digit‑string. (E.g. in bijective base‑2 the number eight would be encoded as $◻c_1{c}_1{c}_2◻$, as $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 $◻$ preceding the digit‑string. The output is $◻c_1{c}_1{c}_1◻$, the bijective base‑2 encoding for 7. Here, $n=2$.

This example translates directly to the equivalent Brainfuck program:

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

References

• . Republished in Yourdon 1979, pp. 13–25

External links

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