Turing machine
Stěžejním úkolem všech vědeckých disciplín, které se zabývají teoretickou stránkou počítačů, je najít dostatečně věrný abstraktní model, na kterém by se daly studovat nejrůznější vlastnosti reálně existujících počítačů, jejich aktuální i potenciální možnosti, principiální omezení apod., a v neposlední řadě také dokazovat různá zajímavá tvrzení - například o tom, že něco nejde spočítat vůbec, zatímco něco jiného nejde spočítat rychleji než za určitou dobu apod.
Zajímavé je, že takových modelů, schopných dostatečně věrně modelovat činnost jakýchkoli počítačů, se našlo více (například tzv. rekurzivní funkce, lambda kalkulus, stroje RAM a RASP a další). Přitom se ale přišlo na velmi zajímavou věc - totiž že všechny tyto modely jsou navzájem rovnocenné (alespoň v tom smyslu, že každý z nich dokáže věrně namodelovat všechny ostatní). V důsledku toho je pak možné vybrat si kterýkoli z těchto vzájemně rovnocenných nástrojů a vystačit s ním - žádný jiný totiž nemůže z principu odhalit něco, co by se s jiným odhalit nedalo.
Modelem, který se mezi všemi vzájemně rovnocennými modely stal nejvíce používaným, je tzv. Turingův stroj (Turing machine), který navrhl anglický matematik Alan M. Turing v roce 1936. Turingův stroj je v mnoha směrech podobný konečnému automatu, který jsme si popisovali minule: má konečný počet stavů, ve kterých se může nacházet, postupně přijímá jednotlivé vstupy, které dostává ze svého okolí, a reaguje na ně přechodem do nového stavu. Na rozdíl od konečného automatu je ale vybaven navíc ještě i nekonečně dlouhou páskou, na kterou si může zapisovat znaky z určité pevně dané abecedy - díky nekonečnosti pásky, kterou si Turingův stroj může podle potřeb posouvat, tak má k dispozici nekonečně velkou paměť. Právě díky tomu, a na rozdíl od konečného automatu, je pak schopen namodelovat jakýkoli výpočet, kterého je v principu schopen kterýkoli počítač.
Právě vyslovené tvrzení si ovšem zaslouží podrobnějšího vysvětlení. Dokázat toto tvrzení nebude nikdy možné - naproti tomu důkaz vzájemné rovnocennosti Turingova stroje s ostatními abstraktními modely počítačů, provést lze. Příčinou je to, že jednotlivé modely jsou exaktně definovány, a příslušné důkazy se tedy mají "o co opřít". Ovšem to, co je "v principu schopen spočítat kterýkoli počítač", je příliš vágním vymezením, které lze interpretovat pouze intuitivně, ale na němž nelze vystavět formální důkaz.
Tuto skutečnost si uvědomil i sám Alan Turing, když v roce 1936 koncipoval svůj abstraktní model počítače (Turingův stroj). Ještě v témže roce pak spolu s dalším anglickým matematikem, Alonzem Churchem, vyslovili domněnku o tom, že počítače (s nekonečně velkou pamětí) a Turingovy stroje jsou vzájemně rovnocenné - tedy že ke každému výpočtu, který je schopen provést počítač, existuje takový Turingův stroj, který jej provede také, a opačně že ke každému Turingovu stroji existuje takový program, který jeho chování bude modelovat.
Domněnka, kterou oba matematici formulovali společně, je dnes známa jako tzv. Churchova teze. Nebude možné ji nikdy dokázat (kvůli intuitivnímu vymezení na straně počítače), ale je dnes všeobecně považována za platnou. Natolik, že se používá jako předpoklad v jiných formálních důkazech - například při důkazu, že neexistuje obecný algoritmus pro ověření správnosti libovolného programu. Ale o tom zase až příště.