


Turingovy stroje vymyslel Alan Turing v 30. letech 20. století jako myšlený stroj (počítač), který by uměl provést jakýkoliv mechanický myšlenkový postup řešící zadaný problém; tedy to, čemu dnes říkáme algoritmus. Turingovy stroje jsou tak jednoduché, že jejich princip lze vysvětlit pomocí tužky a papíru za několik minut. Pomocí Turingových strojů lze také ukázat hranice mechanického myšlení — existují úlohy, ke kterým nikdo nikdy nenapíše počítačový program, který by je uměl řešit. Tak o tom a ještě jiných věcech byla tato přednáška.