Turingov stroj
Turingov stroj je matematický model pre popis algoritmov. Akýkoľvek výpočet, ktorý sa dá vykonať pomocou turingovho stroja sa dá vykonať aj mechanicky.
Základný model turingovho stroja sa skladá z:
- konečnostavovej jednotky
- vstupnej pásky
- čítacej hlavy
Turingov stroj formálne definujeme ako sedmicu: 
kde:
- Q je konečná množina stavov
- Γ je konečná množina abecedy páskových stavov
- b je prázdny symbol. Je podmnožina Γ
množina vstupných symbolov
prechodová funkcia- q0 je počiatočný stav
- F je množina finálnych stavov
Church Turingova téza: "Ľubovoľný proces, ktorý sa dá prirodzene nazvať algoritmom, možno realizovať na turingovom stroji"
