Turingova úplnost - Turing completeness

Pro použití tohoto výrazu v teorii relativní vypočítatelnosti pomocí věšteckých strojů viz Turingova redukce .

V teorii vyčíslitelnosti je systém pravidel manipulace s daty (jako je instrukční sada počítače , programovací jazyk nebo mobilní automat ) považován za Turingův úplný nebo výpočetně univerzální, pokud jej lze použít k simulaci jakéhokoli Turingova stroje . To znamená, že tento systém je schopen rozpoznat nebo rozhodnout jiné sady pravidel pro manipulaci s daty. Úplnost Turing se používá jako způsob, jak vyjádřit sílu takové sady pravidel pro manipulaci s daty. Prakticky všechny programovací jazyky jsou dnes Turing-Complete. Pojem je pojmenován po anglickém matematikovi a informatikovi Alanu Turingovi .

Souvisejícím konceptem je Turingova ekvivalence  - dva počítače P a Q se nazývají ekvivalentní, pokud P může simulovat Q a Q může simulovat P. Církevně -Turingova teze předpokládá, že jakoukoli funkci, jejíž hodnoty lze vypočítat pomocí algoritmu, lze vypočítat pomocí Turingův stroj, a proto, pokud může jakýkoli počítač v reálném světě simulovat Turingův stroj, je to Turingův ekvivalent k Turingovu stroji. Univerzální Turingův stroj může být použit k simulaci jakýkoliv stroj Turingův a potažmo na výpočetní aspekty případného reálného světa počítači.

Abychom ukázali, že je něco Turing-Complete, stačí ukázat, že to lze použít k simulaci nějakého systému Turing-Complete. Například imperativní jazyk je Turingově úplný, pokud má podmíněné větvení (např. Příkazy „if“ a „goto“ nebo instrukce „větev pokud nula“; viz počítač s jednou instrukcí ) a schopnost změnit libovolný množství paměti (např. schopnost udržovat libovolný počet datových položek). Žádný fyzický systém samozřejmě nemůže mít nekonečnou paměť; ale pokud je omezení konečné paměti ignorováno, většina programovacích jazyků je jinak Turing-Complete.

Nematematické využití

Pojmy „Turing-Complete“ a „Turing-equivalent“ v hovorovém používání znamenají, že jakýkoli univerzální počítač nebo počítačový jazyk v reálném světě může přibližně simulovat výpočetní aspekty jakéhokoli jiného univerzálního počítače v reálném světě nebo počítačový jazyk.

Skutečné počítače, které byly dosud postaveny, lze funkčně analyzovat jako Turingův stroj s jednou páskou („páska“ odpovídající jejich paměti); související matematika se tedy může aplikovat abstrakcí jejich provozu dostatečně daleko. Skutečné počítače však mají omezené fyzické zdroje, takže jsou pouze lineárně ohraničeným automatem . Naproti tomu je univerzální počítač definován jako zařízení s instrukční sadou Turing-Complete, nekonečnou pamětí a neomezeným dostupným časem.

Formální definice

V teorii vyčíslitelnosti se k popisu výpočetní síly výpočetního systému (jako je abstraktní stroj nebo programovací jazyk ) používá několik úzce souvisejících termínů :

Turingova úplnost
Výpočtový systém, který dokáže vypočítat každou Turingovu výpočetní funkci, se nazývá Turing-Complete (nebo Turing-silný). Alternativně je takový systém ten, který může simulovat univerzální Turingův stroj .
Turingova ekvivalence
Systém Turing-Complete se nazývá ekvivalent Turinga, pokud každá funkce, kterou dokáže vypočítat, je také Turing-vypočítatelná; tj. počítá přesně stejnou třídu funkcí jako Turingovy stroje . Alternativně je systém ekvivalentní Turingu systém, který může simulovat a být simulován univerzálním Turingovým strojem. (Všechny známé fyzicky implementovatelné systémy Turing-Complete jsou ekvivalentem Turinga, což přidává podporu tezi Church-Turing .)
(Výpočetní) univerzálnost
Systém se nazývá univerzální s ohledem na třídu systémů, pokud dokáže vypočítat všechny funkce spočítatelné systémy v této třídě (nebo může simulovat každý z těchto systémů). Termín univerzálnost se obvykle mlčky používá s ohledem na třídu systémů Turing-Complete. Termín „slabě univerzální“ se někdy používá k rozlišení systému (např. Buněčného automatu ), jehož univerzálnosti je dosaženo pouze úpravou standardní definice Turingova stroje tak, aby zahrnoval vstupní toky s nekonečně mnoha 1 s.

Dějiny

Úplnost Turingu je významná v tom, že každý návrh výpočetního zařízení v reálném světě lze simulovat pomocí univerzálního stroje Turing . V tezi Church -Turing se uvádí, že se jedná o matematický zákon - že univerzální Turingův stroj může v zásadě provádět jakýkoli výpočet, jaký umí jakýkoli jiný programovatelný počítač . To neříká nic o úsilí, které je zapotřebí k napsání programu , ani o času, který může stroji trvat výpočet, ani o schopnostech, které stroj může mít a které nemají nic společného s výpočty.

Charles Babbage ‚s analytické motoru (1830), by byli první Turing-kompletní stroj, kdyby byl postaven v době, kdy byl navržen. Babbage ocenil, že stroj byl schopen velkých počtů výpočtů, včetně primitivních logických úvah, ale neocenil, že žádný jiný stroj to neumí lépe. Od třicátých let 19. století do čtyřicátých let minulého století byly stavěny a vylepšovány mechanické počítací stroje, jako jsou sčítače a multiplikátory, ale nemohly provádět podmíněnou větev, a proto nebyly Turingovy.

Na konci 19. století formuloval Leopold Kronecker pojmy spočitatelnosti a definoval primitivní rekurzivní funkce . Tyto funkce lze vypočítat pomocí počítání na dálku, ale na vytvoření univerzálního počítače nestačí, protože instrukce, které je počítají, neumožňují nekonečnou smyčku. Na počátku 20. století vedl David Hilbert program pro axiomatizaci veškeré matematiky s přesnými axiomy a přesnými logickými pravidly dedukce, které by mohly být prováděny strojem. Brzy se ukázalo, že k vytvoření důsledků jakékoli sady axiomů stačí malý soubor pravidel pro odpočet. Tato pravidla prokázal Kurt Gödel v roce 1930 jako dostatečná k produkci každé věty.

Skutečný pojem výpočtu byl izolován brzy poté, počínaje Gödelovou větou o neúplnosti . Tato věta ukázala, že systémy axiomů byly omezeny při úvahách o výpočtu, který odvozuje jejich věty. Church a Turing nezávisle prokázali, že Hilbertův Entscheidungsproblem (problém s rozhodováním) je neřešitelný, čímž identifikovali výpočetní jádro věty o neúplnosti. Tato práce spolu s Gödelovou prací o obecných rekurzivních funkcích prokázala, že existují sady jednoduchých instrukcí, které, když se dají dohromady, jsou schopné produkovat jakýkoli výpočet. Gödelova práce ukázala, že pojem výpočtu je v podstatě jedinečný.

V roce 1941 dokončil Konrad Zuse počítač Z3 . Zuse v té době neznal Turingovu práci na vypočítatelnosti. Z3 zejména postrádal vyhrazená zařízení pro podmíněný skok, což znemožňovalo, aby byl Turing dokončen. V roce 1998 však Rojas ukázal, že Z3 je schopen podmíněných skoků, a tedy i Turingova dokončení, tím, že některé jeho funkce použil neúmyslně.

Teorie výpočetnosti

Teorie vypočítatelnosti používá modely výpočtu k analýze problémů a určení, zda jsou vypočítatelné a za jakých okolností. Prvním výsledkem teorie vypočítatelnosti je, že existují problémy, pro které není možné předpovědět, co systém (Turing-úplný) udělá po libovolně dlouhou dobu.

Klasickým příkladem je problém se zastavením : vytvořte algoritmus, který vezme jako vstup program v nějakém jazyce Turing-Complete a některá data, která mají být do tohoto programu přivedena , a určí, zda se program, pracující na vstupu, nakonec zastaví nebo bude pokračovat navždy. Je triviální vytvořit algoritmus, který to dokáže u některých vstupů, ale obecně to udělat nelze. U jakékoli charakteristiky eventuálního výstupu programu není možné určit, zda tato charakteristika bude platit.

Tato nemožnost přináší problémy při analýze počítačových programů v reálném světě. Nelze například napsat nástroj, který zcela chrání programátory před zápisem nekonečných smyček nebo chrání uživatele před zadáváním vstupů, které by způsobovaly nekonečné smyčky.

Místo toho je možné omezit provádění programu pouze na pevně stanovené časové období ( časový limit ) nebo omezit výkon instrukcí řízení toku (například poskytovat pouze smyčky, které iterují položky stávajícího pole). Další věta však ukazuje, že existují problémy řešitelné turingovsky kompletními jazyky, které nelze vyřešit žádným jazykem s pouze schopnostmi konečné smyčky (tj. Jakýkoli jazyk zaručující, že každý program se nakonec zastaví). Takže žádný takový jazyk není Turing-úplný. Například jazyk, ve kterém je zaručeno, že se programy dokončí a zastaví, nemůže vypočítat vypočítatelnou funkci vytvořenou Cantorovým diagonálním argumentem pro všechny vypočítatelné funkce v tomto jazyce.

Turingovy věštkyně

Hlavní článek: stroj Oracle

Počítač s přístupem k nekonečné pásce dat může být výkonnější než Turingův stroj: například páska může obsahovat řešení problému se zastavením nebo jiného Turingově nerozhodnutelného problému. Taková nekonečná páska dat se nazývá Turingův věštec . Ani Turingův věštec s náhodnými daty nelze spočítat ( s pravděpodobností 1 ), protože existuje pouze spočetně mnoho výpočtů, ale nespočetně mnoho věštců. Počítač s náhodným Turingovým orákulem tedy dokáže vypočítat věci, které Turingův stroj neumí.

Digitální fyzika

Viz také: Church – Turingova práce § Filozofické implikace

Všechny známé fyzikální zákony mají důsledky, které lze spočítat pomocí řady aproximací na digitálním počítači. Hypotéza zvaná digitální fyzika uvádí, že to není náhoda, protože samotný vesmír je vypočítatelný na univerzálním Turingově stroji. To by znamenalo, že žádný počítač silnější než univerzální Turingův stroj nelze fyzicky postavit.

Příklady

Výpočtové systémy (algebry, kameny), o nichž se hovoří jako o systémech Turingových, jsou určeny ke studiu teoretické informatiky . Mají být co nejjednodušší, aby bylo snazší porozumět limitům výpočtu. Zde je několik:

Většina programovacích jazyků (jejich abstraktní modely, možná s některými konkrétními konstrukcemi, které předpokládají vynechání konečné paměti), konvenční a nekonvenční, je Turing-Complete. To zahrnuje:

Některé přepisovací systémy jsou Turing-Complete.

Turingova úplnost je spíše abstraktním vyjádřením schopností než předpisem konkrétních jazykových funkcí použitých k implementaci této schopnosti. Funkce používané k dosažení Turingovy úplnosti se mohou značně lišit; Systémy Fortran by k dosažení opakování používaly smyčkové konstrukce nebo případně dokonce příkazy goto ; Haskell a Prolog, téměř bez smyčky, by použili rekurzi . Většina programovacích jazyků popisuje výpočty na von Neumannových architekturách , které mají paměť (RAM a registr) a řídicí jednotku. Díky těmto dvěma prvkům je tato architektura Turingova úplná. I čistě funkční jazyky jsou Turing-úplné.

Úplnost Turing v deklarativním SQL je implementována prostřednictvím rekurzivních běžných výrazů tabulek . Není překvapením, že procedurální rozšíření SQL ( PLSQL atd.) Jsou také Turing-Complete. To ilustruje jeden důvod, proč jsou relativně silné jazyky, které nejsou Turingově úplné, vzácné: čím silnější jazyk zpočátku je, tím jsou úkoly, na které je aplikován, složitější a čím dříve je jeho neúplnost vnímána jako nevýhoda, což podporuje rozšíření, dokud nebude Turing-kompletní.

Netypický lambda kalkul je Turingův úplný, ale mnoho typovaných lambda kalkulů, včetně systému F , není. Hodnota napsaných systémů je založena na jejich schopnosti reprezentovat většinu typických počítačových programů a současně detekovat více chyb.

Pravidlo 110 a Conwayova hra o život , oba mobilní automaty , jsou Turing-Complete.

Neúmyslná úplnost Turinga

Některé hry a další software jsou Turing-Complete úplnou náhodou, tj. Ne záměrně.

Software:

Videohry:

Sociální média:

Karetní hry:

Hry pro nulové osoby (simulace):

Výpočetní jazyky:

Počítačový hardware:

  • x86 instrukce MOV

Biologie:

Jazyky, které nejsou Turingovy

Existuje mnoho výpočetních jazyků, které nejsou Turingovo úplné. Jedním z takových příkladů je sada regulárních jazyků , které jsou generovány regulárními výrazy a které jsou rozpoznávány konečnými automaty . Výkonnější, ale stále ještě ne Turingově úplné rozšíření konečných automatů, je kategorie pushdown automatů a bezkontextových gramatik , které se běžně používají ke generování syntaktických stromů v počáteční fázi kompilace programu . Mezi další příklady patří některé z raných verzí jazyků shaderů pixelů vložených do rozšíření Direct3D a OpenGL .

V celkem funkčních programovacích jazycích, jako jsou Charity a Epigram , jsou všechny funkce úplné a musí být ukončeny. Charity používá typový systém a řídí konstrukty založené na teorii kategorií , zatímco Epigram používá závislé typy . Jazyk LOOP je navržen tak, aby počítal pouze funkce, které jsou primitivní rekurzivní . Všechny tyto vypočítají správné podmnožiny celkových vyčíslitelných funkcí, protože úplná sada celkových vyčíslitelných funkcí není vyčíslitelně vyčíslitelná . Protože jsou všechny funkce v těchto jazycích celkem, nelze na rozdíl od Turingových strojů v těchto jazycích zapisovat algoritmy pro rekurzivně vyčíslitelné sady .

Ačkoli (netypový) lambda kalkul je Turingův-úplný, jednoduše napsaný lambda kalkul není.

Datové jazyky

Pojem úplnosti Turing se nevztahuje na jazyky jako XML , HTML , JSON a YAML , protože se obvykle používají k reprezentaci strukturovaných dat, nikoli k popisu výpočtu. Někdy se jim říká značkovací jazyky , nebo vhodněji „jazyky kontejneru“ nebo „jazyky popisu dat“.

Viz také

Poznámky

Reference

Další čtení

externí odkazy