Co je Turingova úplnost?

Turingova úplnost je, když programovací jazyk je schopen vykonávat funkce Turingova stroje. Toto je koncept velmi základního mechanického počítače, někdy označovaného jako nejjednodušší stroj, který lze považovat za počítač. Prakticky všechny programovací jazyky, které se dnes používají, a teoreticky počítače, které je provozují, mají Turingovu úplnost.

Koncept Turingovy úplnosti pochází od Alana Turinga, britského počítačového vědce, jehož práce zahrnovala dešifrování kódovaných zpráv během druhé světové války. Mezi jeho práce v oblasti výpočetní techniky patřil vývoj filozofie toho, co počítač skutečně dokáže. To zahrnovalo koncept, že počítače fungují jednoduše spuštěním algoritmů. To znamená, že se řídí pevnou sadou pravidel pro zpracování dat a následně pro řešení problémů. To znamená, že počítač „nepřemýšlí“ ani neučiní rozhodnutí, jak může člověk.

Pro ilustraci tohoto konceptu Turing popsal hypotetický stroj, který nazýval „a-stroj“, přičemž „a“ znamená automatický; jiní to později nazvali Turingův stroj. Stroj by zpracoval cívku pásky, která by se mohla pohybovat dozadu nebo vpřed a obsahovala řadu symbolů. Stroj mohl kdykoli zpracovat jeden symbol a v případě potřeby jej upravit. Pro účely tohoto konceptu může být cívka pásky nekonečně dlouhá, což znamená, že paměť počítače nebyla neodmyslitelně omezena. Jedná se o analogii myšlenky, že jakmile má počítač soubor pokynů, které má následovat, množství dat, na které se tyto pokyny mohou použít, podléhá pouze fyzickým omezením.

Je ironií, že většina počítačů dnes nemá Turingovu úplnost. Je tomu tak proto, že mají omezení na úložný prostor, a tedy i data, která mohou zpracovat. Mají také fyzická omezení, zejména to, že se nakonec opotřebují. Je to vlastně programovací jazyk, který má Turingovu úplnost. Z tohoto důvodu počítač, na kterém je spuštěn takový program, není Turingův počítač, ale lze jej použít k simulaci jednoho.

Turingova úplnost by neměla být zaměňována s Turingovým testem. Byl to experiment navržený Turingem, aby se zjistilo, zda počítače dokáží konverzovat v přirozeném jazyce. Princip testu je ten, že pokud člověk nedokáže rozeznat rozdíl mezi textovou konverzací s počítačem a jiným člověkem, počítač projde testem. Zatímco některé počítače prošly testem, když je omezen rozsah konverzovaných subjektů, žádný z nich tak neučinil v neomezené konverzaci.