V informatice a logice se říká , že formální systém je úplný ve smyslu Turingova nebo Turingova-úplného (sledováním anglického Turingova-úplného ), pokud má expresivní sílu přinejmenším rovnocennou s výkonem Turingových strojů . V takovém systému je proto možné naprogramovat jakýkoli Turingův stroj.
Tato představa je relevantní z církevní teze , která předpokládá existenci přirozené představy o vypočítatelnosti. Expresivní síla Turingových strojů se tedy shoduje s expresivní silou rekurzivních funkcí , lambda kalkulu nebo dokonce počítacích strojů .
Ačkoli jsou určité modely výpočtu, nazývané hyperpočítače , přísněji expresivnější než Turingovy stroje, jsou tyto modely spekulací (vyžadujících například provádět nekonečný počet operací nebo počítat na množině čísel. Skutečné) a to není známo, zda jsou fyzicky proveditelné. Za těchto podmínek Churchova teze předpokládá univerzálnost výpočetního modelu Turingova stroje: jakýkoli systém Turing-Complete by byl ve skutečnosti ekvivalentem Turingových strojů.
Stejně jako výpočetní model se říká , že počítačový jazyk je Turingův úplný, pokud umožňuje reprezentovat všechny vypočítatelné funkce ve smyslu Turinga a Církve (bez ohledu na konečnost počítačové paměti).
Někteří autoři berou tuto vlastnost pro definici programovacího jazyka , ale lze zvolit i jiné definice.
Obvyklé programovací jazyky ( C , Java …) jsou Turingovy úplné, protože obsahují všechny ingredience nezbytné pro simulaci univerzálního Turingova stroje (počítat, porovnávat, číst, psát atd.). Jazyk C ++ je také Turingův úplný a podmnožina umožňující generické programování ( šablony ) je také .
Jazyk SQL , původně neúplný v Turingově smyslu, se stal standardem SQL: 1999, který mu umožňoval psát rekurzivní dotazy .
Jazyk LaTeX (od TeXu ), určený pro skládání dokumentů, je také Turing-complete.
Samotný jazyk HTML není Turingův úplný, bylo však prokázáno, že jazyk CSS (ve verzi 3) umožňuje stavět základní buněčný automat kódu 110 (viz pravidlo 110 (en) ), o kterém se ví, že je univerzální. smysl pro Turing. Tyto dva jazyky jsou často neoddělitelné, můžeme dojít k závěru, že HTML + CSS je Turing-complete, a toto spojení proto z něj teoreticky dělá programovací jazyk.
Jazyk Turing-Complete zdědil vlastnosti stroje Turing. Například problém s vypínáním je nerozhodnutelný , takže je nemožné napsat program, který říká, zda libovolný program, který mu byl udělen, končí nebo ne.
Některé jazyky určené k řešení konkrétních problémů nejsou Turingovy úplnosti. Příkladem je systém F , lambda kalkulus. Turing-complete navíc - podle návrhu - nejsou ani jazyky Total (en) , kde všechny výpočty nutně končí (jako jazyk Gallina asistentky Coq proof ). Ty druhé jsou však v praxi schopné vypočítat vše, co nás zajímá, jinými slovy, mohou implementovat všechny funkce, které bychom v praktickém životě mohli potřebovat; výpočty, které jim uniknou, mají buď složitost za hranicí představitelnosti a realizovatelnosti, nebo nekončí. Kompilace pak musí demonstrovat ukončení programů nebo vyžadovat interakci s programátorem pro některé ukázky, ale toto je cena za kvalitu kódu, která je správná z hlediska konstrukce.
Některé hry a software jsou Turing-Complete náhodou, aniž by to jejich autoři chtěli nebo zvážili:
„ Skutečnost, že všechny standardní programovací jazyky přesně vyjadřují třídu částečných rekurzivních funkcí, je často shrnuta tvrzením, že všechny programovací jazyky jsou Turingovy úplné. "
„ Programovací jazyk je jazyk, který je určen k vyjádření počítačových programů a je schopen vyjádřit jakýkoli počítačový program. To není vágní představa. Existuje přesný teoretický způsob, jak určit, zda lze počítačový jazyk použít k vyjádření jakéhokoli programu, konkrétně tím, že se ukáže, že je ekvivalentní univerzálnímu Turingovu stroji. "