コンピューターの理論的模型を発案チューリングの停止問題

チューリングマシンは、無限に伸びたテープと、その上で記号の読み書きをするヘッドおよびそれを制御する有限制御部で構成される。テープはマス目に区切られ、ヘッドはマス目の記号を読み取ったり書き込んだり、左右に動いたりする。およそ計算されうることは、この機械で処理できるとみなされている。チューリングマシンの動作はプログラムで表すこともでき、プログラムと入力データの組を与えて、そのプログラムが表すチューリングマシンがその入力データに対して行う動作を一つの機械で模倣するような万能チューリングマシンが存在する。万能チューリングマシンが、どのようなプログラムとデータに対して停止するかを判定するアルゴリズムがあるか、というのが「停止問題」で、チューリングはこれを否定的に解決した。