P ′ ′ - P′′

P ′ ′ (P double prime^[1]) je primitivní počítač programovací jazyk vytvořil Corrado Böhm^[2][3] v roce 1964 popsat rodinu Turingovy stroje.

Definice

${ textstyle { mathcal {P}} ^ { prime prime}}$ (dále psáno P ′ ′) je formálně definována jako sada slov na abecedě se čtyřmi instrukcemi ${ textstyle {R, lambda, (,) }}$, jak následuje:

Syntax

1. ${ textstyle R}$ a ${ textstyle lambda}$ jsou slova v P ′ ′.
2. Li ${ textstyle q_ {1}}$ a ${ textstyle q_ {2}}$ jsou tedy slova v P ′ ′ ${ textstyle q_ {1} q_ {2}}$ je slovo v P ′ ′.
3. Li ${ textstyle q}$ je tedy slovo v P ′ ′ ${ textstyle (q)}$ je slovo v P ′ ′.
4. Pouze slova odvozitelná z předchozích tří pravidel jsou slova v P ′ ′.

Sémantika

• ${ textstyle { Box, c_ {1}, c_ {2}, ldots, c_ {n} }}$ je pásová abeceda a Turingův stroj s levou nekonečnou páskou, ${ textstyle Box}$ být prázdný symbol, ekvivalent k ${ textstyle c_ {0}}$.
• Všechny pokyny v P ′ ′ jsou obměny sady ${ textstyle X}$ všech možných konfigurací pásky; to znamená všechny možné konfigurace jak obsahu pásky, tak polohy hlavy pásky.
• ${ textstyle alpha}$ je predikát říká, že aktuální symbol není ${ textstyle Box}$. Není to instrukce a nepoužívá se v programech, ale místo toho se používá k definování jazyka.
• ${ textstyle R}$ znamená přesunout hlavu pásky doprava o jednu buňku (pokud je to možné).
• ${ textstyle lambda}$ znamená nahradit aktuální symbol ${ textstyle c_ {i}}$ s ${ textstyle c _ {(i + 1) { bmod {(}} n + 1)}}$a poté posuňte hlavu pásky doleva o jednu buňku.
• ${ textstyle q_ {1} q_ {2}}$ znamená složení funkce ${ textstyle q_ {2} circ q_ {1}}$. Jinými slovy, instrukce ${ textstyle q_ {1}}$ se provádí dříve ${ textstyle q_ {2}}$.
• ${ textstyle (q)}$ znamená iterovat ${ textstyle q}$ v zatímco smyčka, s podmínkou ${ textstyle alpha}$.

Vztah k jiným programovacím jazykům

• P ′ ′ byl první “JÍT DO - bez imperativu strukturované programování jazyk k prokázání Turing-kompletní^[2][3]
• The Brainfuck jazyk (kromě jeho I / O příkazů) je menší neformální variace P ′ ′. Böhm dává explicitní P ′ ′ programy pro každou ze sady základních funkcí dostatečných k výpočtu jakékoli vypočítatelná funkce, pouze pomocí ${ textstyle (}$, ${ textstyle)}$ a čtyři slova ${ textstyle r, r ^ { prime}, L, R}$ kde ${ textstyle r equiv lambda R, r ^ { prime} equiv r ^ {n}}$ s ${ textstyle r ^ {n}}$ označující ${ textstyle n}$th opakovat z ${ textstyle r}$, a ${ textstyle L equiv r ^ { prime} lambda}$. Toto jsou ekvivalenty šesti příslušných příkazů Brainfuck [, ], +, -, <, >. Všimněte si, že od té doby ${ textstyle c_ {n + 1} equiv c_ {0} equiv Box}$, zvyšující aktuální symbol ${ textstyle n}$ times will wrap around so that the result is to "decrement" the symbol in the current cell by one (${ textstyle r ^ { prime}}$).

Ukázkový program

Böhm^[2] dává následující program pro výpočet předchůdce (X-1) celého čísla X > 0:

${ displaystyle R (R) L (r ^ { prime} (L (L)) r ^ { prime} L) Rr}$

což se překládá přímo na ekvivalent Brainfuck program:

>[>]<[−[<[<]]−<]>+

Program očekává, že bude zastoupeno celé číslo bijective base-k notace, s ${ textstyle c_ {1}, c_ {2} ldots, c_ {k}}$ kódování číslic ${ textový styl 1,2, ldots, k}$ respektive a mít ${ textstyle Box}$ před a za číslicovým řetězcem. (Např. V bijektivu base-2 by číslo osm bylo zakódováno jako ${ textstyle Box c_ {1} c_ {1} c_ {2} Box}$, protože 8 v bijektivu base-2 je 112.) Na začátku a na konci výpočtu je pásková hlava na ${ textstyle Box}$ před číslicovým řetězcem.

Reference

Webové odkazy

• P ′ ′Online tlumočník: Demonstrace iterativu 99 lahví piva píseň vyložena v 337568 P ′ ′ instrukce.