Jump to content

P′′

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by OlliverWithDoubleL (talk | contribs) at 10:16, 11 December 2022 (Fixed typo). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

Definition

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

Syntax

  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

  • 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

  • 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

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 bijective base-2 is 112.) At the beginning and end of the computation, the tape-head is on the preceding the digit-string.

References

  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.)