P′′

P′′ er et programmeringssprog på lavt niveau skabt i 1964 af Corrado Böhm .

Definition

P′′ er formelt defineret som et sæt alfabetiske ord med 4 instruktioner {R, λ, (, )} som følger:

Syntaks

1. R og λ er ord.
2. Hvis p og q er ord, så er pq et ord.
3. Hvis q er et ord, så er (q) et ord.
4. Resten af ​​tegnsekvenserne er ikke ord.

Semantik

1. {a0, a1, ..., an} (n ≥ 1)- alfabetet af et uendeligt bånd (svarende til båndet på en Turing-maskine), - et tomt symbol.a0
2. R - flytter tapehovedet en celle til højre.
3. λ - erstat det nuværende tegn med ( erstattes af ) og flyt hovedet en celle til venstre.aiai+1ana0
4. (q) — gentag operationen/operationerne q , indtil værdien af ​​den aktuelle celle er lig med .a0
5. Operationer udføres fra venstre mod højre i den rækkefølge, de er skrevet, indtil intet er tilbage til højre.

Yderligere fakta

1. P′′ er det første Turing-komplette programmeringssprog uden GOTO-sætningen .
2. Brainfuck sprogkommandoer (med undtagelse af input og output) kan oversættes til P′′ og omvendt: