P''

From Esolang

P′′ is a primitive programming language created by Corrado Böhm ^1,2 in 1964 to describe a family of Turing machines.

Contents 1 Syntax 2 Semantics 3 Relation to other programming languages 4 References 5 External resources

[edit] Syntax

1. R and λ are words in P′′.
2. If p and q are words in P′′, then pq 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′′.

[edit] Semantics

• {a₀, a₁, ..., a_n}(n ≥ 1) is the tape-alphabet of a Turing machine with left-infinite tape, a₀ being the blank symbol.
• R means move the tape-head rightward one cell (if any).
• λ means replace the current symbol a_i by a_i+1 (taking a_n+1 = a₀), and then move the tape-head leftward one cell.
• (q) means iterate q in a while-loop, with condition that the current symbol is not a₀.
• A program is a word in P′′. Execution of a program proceeds left-to-right, executing R, λ, and (q) as they are encountered, until there is nothing more to execute.

[edit] Relation to other programming languages

Brainfuck (apart from its I/O instructions) is a simple informal variation of Böhm's P′′. Böhm¹ gives explicit P′′ programs for each of a set of basic functions sufficient to compute any partial recursive function -- and these programs are constructed entirely from six P′′ words precisely equivalent to the respective Brainfuck commands +, -, <, >, [, and ].

P′′ was the first "goto-less" or "structured programming" language proved² to be functionally equivalent to languages that use gotos.

[edit] References

1. Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, (July 1964), 187-194.
2. 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 seminal paper on the structured program theorem.)

[edit] External resources

• P′′ at Wikipedia describes an explicit example program from Böhm¹.

• Fm Languages has some discussion of P′′ as adapted to Turing machines with a right-infinite (or optionally both-ways-infinite) tape.