P′′

P′′
Paradigm imperative, structured
Designed by Corrado Böhm
First appeared 1964
untyped

P′′ is a primitive computer programming language created by Corrado Böhm[1][2] in 1964 to describe a family of Turing machines.

Definition

\mathcal{P}^{\prime\prime} (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

Relation to other programming languages

Example program

Böhm[1] 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 a1, ..., an coding the digits 1,...,n, respectively, and to have an a0 before and after the digit-string. (E.g. in bijective base-2, the number eight would be encoded as a0a1a1a2a0, because 8 = 1*22 + 1*21 + 2*20.) At the beginning and end of the computation, the tape-head is on the a0 preceding the digit-string.

References

  1. 1.0 1.1 1.2 1.3 Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
  2. 2.0 2.1 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 most-cited paper on the structured program theorem.)