BlooP a FlooP - BlooP and FlooP

BlooP a FlooP jsou jednoduché programovací jazyky navrhl Douglas Hofstadter pro ilustraci bodu ve své knize Gödel, Escher, Bach.[1] BlooP je programovací jazyk, který není úplný Turing jehož hlavní struktura toku řízení je omezená smyčka (tj. rekurze není povoleno). Všechny programy v daném jazyce musí být ukončeny a tento jazyk může pouze vyjadřovat primitivní rekurzivní funkce.[2]

FlooP je identický s BlooP, kromě toho, že podporuje neomezené smyčky; je to Turingův úplný jazyk a dokáže vyjádřit vše vypočítatelné funkce. Může například vyjádřit Ackermannova funkce, které (nebýt primitivní rekurzivní) nelze v BlooP zapsat. Výpůjčka ze standardní terminologie v matematická logika,[3][4] Hofstadter volá neomezené smyčky FlooP MU-smyčky. Stejně jako všechny programovací jazyky Turing-complete i FlooP trpí zastavení problému: programy se nemusí ukončit a obecně není možné rozhodnout, které programy ano.

BlooP a FlooP lze považovat za modely výpočtu, a někdy byly použity při výuce vypočítatelnosti.[5]

BlooP příklady

Jediný proměnné jsou výstup (návratová hodnota procedury) a buňka(i) (neomezená posloupnost proměnných přirozeného čísla, indexovaných konstantami, jako v Neomezený registrační stroj[6]). Jediný operátory jsou ⇐ (úkol ), + (přidání), × (násobení), < (méně než), > (větší než) a = (rovná se).

Každý program používá pouze konečný počet buněk, ale čísla v buňkách mohou být libovolně velká. Datové struktury, jako jsou seznamy nebo komíny, lze zpracovat interpretací čísla v buňce konkrétními způsoby, tj. Pomocí Gödelovo číslování možné struktury.

Konstrukce řízení toku zahrnují ohraničené smyčky, podmíněné příkazy, PŘERUŠIT vyskočí ze smyček a PŘESTAT vyskočí z bloků. BlooP nepovoluje rekurzi, neomezené skoky ani nic jiného, ​​co by mělo stejný účinek jako neomezené smyčky FlooP. Pojmenované procedury lze definovat, ale mohou volat pouze dříve definované procedury.[7]

Faktoriální funkce

DEFINUJTE POSTUP FAKTORIÁLNÍ [N]: BLOK 0: ZAČÁTEK VÝSTUPU ⇐ 1; CELL (0) ⇐ 1; SLUČKA NEJVĚTŠÍ ČAS: BLOK 1: ZAČÁTEK VÝSTUPU P VÝSTUP × BUNKA (0); CELL (0) ⇐ CELL (0) + 1; BLOK 1: KONEC; BLOK 0: KONEC.

Funkce odčítání

Toto není vestavěná operace a (je definována na přirozených číslech) nikdy nedává negativní výsledek (např. 2 - 3: = 0). Všimněte si, že VÝSTUP začíná na 0, jako všechny ostatní BUŇKAs, a proto nevyžaduje žádnou inicializaci.

DEFINUJTE POSTUP MÍNUS [M, N]: BLOK 0: ZAČNĚTE, POKUD M 
Příklad FlooP
Níže uvedený příklad, který implementuje Ackermannova funkce, spoléhá na simulaci zásobníku pomocí Gödelovo číslování: tj. na dříve definované číselné funkce TLAČIT, POP, a HORNÍ uspokojující PUSH [N, S]> 0, TOP [PUSH [N, S]] = N, a POP [PUSH [N, S]] = S. Protože neomezený MU-LOOP je použito, nejedná se o legální program BlooP. The UKONČIT BLOK pokyny v tomto případě přeskočte na konec bloku a opakujte smyčku, na rozdíl od PŘERUŠIT, který opouští smyčku.[3]
DEFINUJTE POSTUP ACKERMANN [M, N]: BLOK 0: ZAČÁTEK BUNKY (0) ⇐ M; VÝSTUP ⇐ N; CELL (1) ⇐ 0; MU-LOOP: BLOK 1: ZAČNĚTE, POKUD BUDE (0) = 0, POTOM: BLOK 2: ZAČÍNAT VÝSTUP ⇐ VÝSTUP + 1; IF CELL (1) = 0, THEN: ABORT LOOP 1; CELL (0) ⇐ TOP [CELL (1)]; CELL (1) ⇐ POP [CELL (1)]; UKONČIT BLOK 1; BLOK 2: END IF OUTPUT = 0, POTOM: BLOCK 3: BEGIN OUTPUT ⇐ 1; CELL (0) ⇐ MINUS [CELL (0), 1]; UKONČIT BLOK 1; BLOK 3: KONEC VÝSTUPU ⇐ MÍNUS [VÝSTUP, 1]; CELL (1) ⇐ PUSH [MINUS [CELL (0), 1], CELL (1)]; BLOK 1: KONEC; BLOK 0: KONEC.
Viz také
Reference
  1. ^ Douglas Hofstadter (1979), Gödel, Escher, Bach Základní knihy, kapitola XIII.
  2. ^ Stanfordská encyklopedie filozofie: Vyčíslitelnost a složitost
  3. ^ A b Hofstadter (1979), str. 424.
  4. ^ Thomas Forster (2003), Logika, indukce a sady, Cambridge University Press, str. 130.
  5. ^ David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, Přednáška 27.
  6. ^ Hofstadter tyto buňky označuje jako soubor „pomocných proměnných“.
  7. ^ Hofstadter (1979), str. 413.
externí odkazy