Turingův stroj
teoretický model počítače popsaný matematikem Alanem Turingem / From Wikipedia, the free encyclopedia
Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem, který se používá pro modelování algoritmů v teorii vyčíslitelnosti.
Tento článek potřebuje úpravy.
Skládá se z řídicí jednotky s konečným počtem stavů, konečné množiny pravidel, která definují přechodovou funkci, a pravostranně nekonečné pásky pro vstup a zápis mezivýsledků.
Jeden ze způsobů vyjádření Churchovy–Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj.
Od výpočetní síly Turingova stroje se odvozuje turingovská úplnost: turingovsky úplné jsou právě ty programovací jazyky nebo počítače, které mají stejnou výpočetní sílu jako Turingův stroj.