P′′ Explained

P′′
Released:1964
Typing:untyped
Influenced:Brainfuck

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

Definition

\mathcal^ (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet \, 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

Relation to other programming languages

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\primeL)Rr

which translates directly to the equivalent Brainfuck program: >[>]<[−[<[<]]−<]>+The program expects an integer to be represented in bijective base-k notation, with c_1, c_2 \ldots, c_k encoding the digits 1, 2, \ldots, k respectively, and to have \Box before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as \Box c_1 c_1 c_2 \Box, because 8 in base-2 is 100, reverse the digits, and add one to each of them.) At the beginning and end of the computation, the tape-head is on the \Box preceding the digit-string.

External links


Notes and References

  1. Web site: PDBL: A tool for Turing machine simulation. 4 September 2021.
  2. Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
  3. 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.)