Co je Turingova úplnost?

Turingová úplnost je, když je programovací jazyk schopen vykonávat funkce Turingova stroje.Toto je koncept pro velmi základní mechanický počítač, někdy popsaný 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 řídí, mají úplnost.

Koncept Turingovy úplnosti pochází od Alan Turing, 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 prací na výpočtu patřil vývoj filozofie toho, co by počítač skutečně mohl udělat.To zahrnovalo koncept, že počítače fungují jednoduše spuštěním algoritmů.To znamená, že dodržují pevnou sadu pravidel ke zpracování dat a následně řeší problémy.To znamená, že počítač nemyslí ani se rozhoduje, jak může člověk.Ostatní to později nazvali Turingovým strojem.Stroj by zpracoval naviják pásky, který by se mohl pohybovat zpět nebo vpřed a obsahovat řadu symbolů.V každém okamžiku mohl stroj zpracovat jeden symbol a v případě potřeby jej změnit.Pro účely konceptu by mohla být naviják pásky nekonečně dlouhý, což znamená, že paměť počítače nebyla ze své podstaty omezená.Toto je analogie pro myšlenku, že jakmile má počítač sadu pokynů, které lze dodržovat, množství dat, na které může tyto pokyny použít, podléhá pouze fyzickým limitům.Je to proto, že mají omezení dostupného úložného prostoru, a tedy data, která mohou zpracovat.Mají také fyzická omezení, zejména to, že nakonec budou opotřebovat.Ve skutečnosti je to programovací jazyk, který má Turingova úplnost.Z tohoto důvodu není počítač s takovým programem počítačem Turing, ale lze jej použít k simulaci jednoho.

Turingová úplnost by neměla být zaměňována s Turingovým testem.To byl experiment navržený Turingem, aby zjistil, zda počítače mohou konverzovat v přirozeném jazyce.Princip testu je, že pokud člověk nedokáže rozeznat rozdíl mezi konverzací pouze pro text 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 konverzačních předmětů, žádný z nich to neudělal v neomezené konverzaci.