P′′

Short description: Primitive programming language created in 1964

P′′Paradigm| Imperative, structured

|

Designed by| Corrado Böhm
First appeared| 1964
Typing discipline| untyped
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.

## Contents

* 1 Definition
* 1.1 Syntax
* 1.2 Semantics
* 2 Relation to other programming languages
* 3 Example program
* 4 References
* 5 External links

## Definition

𝒫′′ (hereinafter 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 q1 and q2 are words in P′′, then q1q2 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

* {◻,c1,c2,…,cn} is the tape-alphabet of a Turing machine with left-infinite tape, ◻ being the blank symbol, equivalent to c0.
* All instructions in P′′ are permutations of the set X 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.
* R means move the tape-head rightward one cell (if possible).
* λ means replace the current symbol ci with c(i+1)mod(n+1), and then move the tape-head leftward one cell.
* q1q2 means the function composition q2∘q1. In other words, the instruction q1 is performed before q2.
* (q) means iterate q 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 r,r′,L,R where r≡λR,r′≡rn with rn denoting the nth iterate of r, and L≡r′λ. These are the equivalents of the six respective Brainfuck commands [, ], +, -, <, >. Note that since cn+1≡c0≡◻, incrementing the current symbol n times will wrap around so that the result is to "decrement" the symbol in the current cell by one (r′).

## Example program

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

R(R)L(r′(L(L))r′L)Rr

which translates directly to the equivalent Brainfuck program:

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

The program expects an integer to be represented in bijective base-k notation, with c1,c2…,ck encoding the digits 1,2,…,k respectively, and to have ◻ before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as ◻c1c1c2◻, 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. https://github.com/Pbtflakes/pdbl.
2. ↑ 2.0 2.1 2.2 Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
3. ↑ 3.0 3.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.)

## External links

* P′′Online interpreter: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/P′′. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=P′′&oldid=226144"