P prime prime

The title of this article is incorrect due to technical limitations. The correct title is {{{title|{{{1}}}}}}.

<math>\mathcal{P}^{\prime\prime}</math> is a primitive programming language created by Corrado Böhm ^1,2 in 1964 to describe a family of Turing machines.

Contents 1 Definition 1.1 Syntax 1.2 Semantics 2 Relation to other programming languages 3 Example program 4 References 5 External resources

Definition

<math>\mathcal{P}^{\prime\prime}</math> (hereafter written 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 p and q are words in P′′, then pq 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

• {a₀, a₁, ..., a_n}(n ≥ 1) is the tape-alphabet of a Turing machine with left-infinite tape, a₀ being the blank symbol.
• R means move the tape-head rightward one cell (if any).
• λ means replace the current symbol a_i by a_i+1 (taking a_n+1 = a₀), and then move the tape-head leftward one cell.
• (q) means iterate q in a while-loop, with condition that the current symbol is not a₀.
• A program is a word in P′′. Execution of a program proceeds left-to-right, executing R, λ, and (q) as they are encountered, until there is nothing more to excecute.

Relation to other programming languages

• P′′ was the first "GOTO-less" imperative structured programming language to be proved^1,2 Turing-complete.

• Brainfuck (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 partial recursive function, using only the six words r ≡ λR, r′ ≡ rⁿ, L ≡ r′λ, R, (, ), which are the equivalents of the respective brainfuck commands +, -, <, >, [, ].

Example program

Böhm¹ gives the following program to compute the predecessor (x-1) of an integer x > 0:

R ( R ) L ( r' ( L ( L ) ) r' L ) R r

which translates directly to the equivalent brainfuck program

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

The program expects an integer to be represented in bijective base-n notation, with a₁, ..., a_n coding the digits 1,...,n, respectively, and to have an a₀ before and after the digit-string. (E.g. in bijective base-2, the number eight would be encoded as a₀a₁a₁a₂a₀, because 8 = 1*2^2 + 1*2^1 + 2*2^0.)  At the beginning and end of the computation, the tape-head is on the a₀ preceding the digit-string.

References

1. Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 187-194, July 1964.
2. Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the seminal paper on the structured program theorem.)

External resources

• The Fm languages are variations of P′′ as adapted to Turing machines with a right- (or optionally both-ways-) infinite tape.