![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png&w=640&q=50)
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.
![ikona](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/48px-Broom_icon.svg.png)
Tento článek potřebuje úpravy.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png)
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.