チューリングマシンとは現在のコンピューターの原型ともいえるもの。現在のノイマン型コンピューターに相当する。
チューリングマシンを適切に設計すれば、いかなるアルゴリズムも実行可能であること、しかしチューリングマシンが有限時間で停止するかどうかはわからない(停止性問題)ことを示した。