P′′

P′′ är ett programmeringsspråk på låg nivå skapat 1964 av Corrado Böhm .

Definition

P′′ definieras formellt som en uppsättning alfabetiska ord med 4 instruktioner {R, λ, (, )} enligt följande:

Syntax

1. R och λ är ord.
2. Om p och q är ord, så är pq ett ord.
3. Om q är ett ord, så är (q) ett ord.
4. Resten av teckensekvenserna är inte ord.

Semantik

1. {a0, a1, ..., an} (n ≥ 1)- alfabetet för ett oändligt band (liknande bandet på en Turing-maskin), - en tom symbol.a0
2. R - Flyttar bandhuvudet en cell åt höger.
3. λ - ersätt det nuvarande tecknet med ( ersätts av ) och flytta huvudet en cell åt vänster.aiai+1ana0
4. (q) — upprepa operationen/operationerna q tills värdet på den aktuella cellen är lika med .a0
5. Operationer utförs från vänster till höger i den ordning som de skrivs, tills ingenting finns kvar till höger.

Ytterligare fakta

1. P′′ är det första Turing-kompletta programmeringsspråket utan GOTO-satsen .
2. Brainfuck språkkommandon (med undantag för input och output) kan översättas till P′′ och vice versa: