Teória vypočítateľnosti

Dôležitou súčasťou teoretickej informatiky problematika Turingových strojov. Tento výpočtový model má dve základné vlastnosti: Tak ako každý iný počı́tačový program, i softvér Turingovho stroja je zložený z inštrukciı́, v jeho prı́pade sú však všetky jediného typu. Každý iný (doteraz známy) počı́tačový program možno bez straty informácie transformovať na program nejakého Turingovho stroja. Kým druhá črta redukuje otázku, čo nedokáže počı́tač, na otázku, čo nedokáže Turingov stroj, prvá umožňuje oveľa jednoduchšı́ výskum takejto otázky. Pomocou tohto výpočtového modelu tak môžeme nájsť konkrétne problémy, s ktorými si žiaden automat nikdy neporadı́ (azda najznámejšı́ je problém zastavenia sa Turingovho stroja). Ich existencia dokazuje principiálnu obmedzenosť (nielen ideálnych) výpočtových prostriedkov, a tak povzbudzuje kritickosť i pokoru nášho myslenia.