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.

P′′
ParadigmImperative, structured
Designed byCorrado Böhm
First appeared1964
Typing disciplineuntyped
Dialects
Brainfuck
Influenced
Brainfuck

Definition

edit

  (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet  , as follows:

Syntax

edit
  1.   and   are words in P′′.
  2. If   and   are words in P′′, then   is a word in P′′.
  3. If   is a word in P′′, then   is a word in P′′.
  4. Only words derivable from the previous three rules are words in P′′.

Semantics

edit
  •   is the tape-alphabet of a Turing machine with left-infinite tape,   being the blank symbol, equivalent to  .
  • All instructions in P′′ are permutations of the set   of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head.
  •   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.
  •   means move the tape-head rightward one cell (if possible).
  •   means replace the current symbol   with  , and then move the tape-head leftward one cell.
  •   means the function composition  . In other words, the instruction   is performed before  .
  •   means iterate   in a while loop, with the condition  .

Relation to other programming languages

edit
  • P′′ was the first "GOTO-less" imperative structured programming language to be proven Turing-complete[2][3]
  • 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   where   with   denoting the  th iterate of  , and  . These are the equivalents of the six respective Brainfuck commands [, ], +, -, <, >. Note that since  , incrementing the current symbol   times will wrap around so that the result is to "decrement" the symbol in the current cell by one ( ).

Example program

edit

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

 

which translates directly to the equivalent Brainfuck program:

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

The program expects an integer to be represented in bijective base-k notation, with   encoding the digits   respectively, and to have   before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as  , 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   preceding the digit-string.

References

edit
  1. ^ "PDBL: A tool for Turing machine simulation". 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.)
edit