en.wikipedia.org

P′′ - Wikipedia

From Wikipedia, the free encyclopedia

P′′
ParadigmImperative, structured
Designed byCorrado Böhm
First appeared1964
Typing disciplineuntyped
Dialects
Brainfuck
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.

{\textstyle {\mathcal {P}}^{\prime \prime }} (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet {\textstyle \{R,\lambda ,(,)\}}, as follows:

  1. {\textstyle R} and {\textstyle \lambda } are words in P′′.
  2. If {\textstyle q_{1}} and {\textstyle q_{2}} are words in P′′, then {\textstyle q_{1}q_{2}} is a word in P′′.
  3. If {\textstyle q} is a word in P′′, then {\textstyle (q)} is a word in P′′.
  4. Only words derivable from the previous three rules are words in P′′.

Relation to other programming languages

[edit]

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

{\displaystyle R(R)L(r^{\prime }(L(L))r^{\prime }L)Rr}

which translates directly to the equivalent Brainfuck program:

The program expects an integer to be represented in bijective base-k notation, with {\textstyle c_{1},c_{2}\ldots ,c_{k}} encoding the digits {\textstyle 1,2,\ldots ,k} respectively, and to have {\textstyle \Box } before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as {\textstyle \Box c_{1}c_{1}c_{1}c_{2}\Box }, because 8 in base-2 is 1000, reverse the digits, and add one to each of them.) At the beginning and end of the computation, the tape-head is on the {\textstyle \Box } preceding the digit-string.

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