計算可能性理論
神託機械とは、特定の決定不能な問題への解を「神託」として与える機械である。例えば、チューリングマシンに「停止問題の神託機械」が付属していれば、与えられた入力についてそのチューリングマシンが停止するかどうかは即座に判定できる。このような機械は再帰理論の中心的話題である。
これも有限状態機械に似ているが、入力が「テープ」の形式になっていて、読むだけでなく書くこともでき、テープを送ったり巻き戻したりして読み書きの位置を決めることができる。テープのサイズは任意である。チューリングマシンは時間さえかければ、かなり複雑な問題も解くことができる。このモデルは計算機科学では最も重要な計算モデルであり、資源の限界がない計算をシミュレートしたものである。
アロンゾ・チャーチとスティーブン・コール・クリーネが開発したラムダ計算により、計算可能性理論の定式化に重要な役割を果たした。アラン・チューリングは現代計算機科学の父とされる人物であり、チューリングマシンなど計算可能性理論にも数々の重要な足跡を残している(、1936年)。