P′′

P′′ on Corrado Böhmin vuonna 1964 luoma matalan tason ohjelmointikieli .

Määritelmä

P′′ määritellään muodollisesti 4 käskyn {R, λ, (, )} aakkosisten sanojen joukoksi seuraavasti:

Syntaksi

1. R ja λ ovat sanoja.
2. Jos p ja q ovat sanoja, niin pq on sana.
3. Jos q on sana, niin (q) on sana.
4. Loput merkkijonot eivät ole sanoja.

Semantiikka

1. {a0, a1, ..., an} (n ≥ 1)- äärettömän nauhan aakkoset (samanlainen kuin Turingin koneen nauha), - tyhjä symboli.a0
2. R - siirtää nauhan päätä yhden solun oikealle.
3. λ - korvaa nykyinen merkki merkillä ( korvataan merkillä ) ja siirrä päätä yhden solun vasemmalle.aiai+1ana0
4. (q) — toista operaatio(t) q , kunnes nykyisen solun arvo on yhtä suuri kuin .a0
5. Toiminnot suoritetaan vasemmalta oikealle siinä järjestyksessä, jossa ne kirjoitetaan, kunnes oikealle ei jää mitään.

Muita faktoja

1. P′′ on ensimmäinen Turingin täydellinen ohjelmointikieli ilman GOTO-käskyä .
2. Brainfuck- kielen komennot (syöttöä ja lähtöä lukuun ottamatta) voidaan kääntää P′′:ksi ja päinvastoin: