P′′
P′′ is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines.
Definition
(hereafter written P′′) is formally defined as a set of words on the four-instruction alphabet {R, λ, (, )}, as follows:
Syntax
R and λ are words in P′′.
If p and q are words in P′′, then pq is a word in P′′.
If q is a word in P′′, then (q) is a word in P′′.
Only words derivable from the previous three rules are words in P′′.
Semantics
{a0, a1, ..., an}(n ≥ 1) is the tape-alphabet of a Turing machine with left-infinite tape, a0 being the blank symbol.
R means move the tape-head rightward one cell (if any).
λ means replace the current symbol ai by a(i+1) mod (n+1), 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 a0.
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.