P′′

P′′ este un limbaj de programare de nivel scăzut creat în 1964 de Corrado Böhm .

Definiție

P′′ este definit formal ca un set de cuvinte alfabetice cu 4 instrucțiuni {R, λ, (, )} după cum urmează:

Sintaxă

1. R și λ sunt cuvinte.
2. Dacă p și q sunt cuvinte, atunci pq este un cuvânt.
3. Dacă q este un cuvânt, atunci (q) este un cuvânt.
4. Restul secvențelor de caractere nu sunt cuvinte.

Semantică

1. {a0, a1, ..., an} (n ≥ 1)- alfabetul unei benzi infinite (asemănător cu banda unei mașini Turing), - un caracter gol.a0
2. R - mută capul benzii cu o celulă la dreapta.
3. λ - înlocuiți caracterul curent cu ( este înlocuit cu ) și mutați capul cu o celulă la stânga.aiai+1ana0
4. (q) — repetați operația(ele) q până când valoarea celulei curente este egală cu .a0
5. Operațiile se efectuează de la stânga la dreapta în ordinea în care sunt scrise, până când nu rămâne nimic în dreapta.

Fapte suplimentare

1. P′′ este primul limbaj de programare Turing complet fără instrucțiunea GOTO .
2. Comenzile limbajului Brainfuck (cu excepția intrării și ieșirii) pot fi traduse în P′′ și invers: