チューリングは機械的なプロセスで解くことが出来ない問題(停止性問題)があることを証明したわけなのだが、その過程でチューリングは、無制限のテープと有限状態オートマトンから成る計算モデル「チューリングマシン」を提示し、さらに、「任意のチューリングマシンを模擬できるチューリングマシン」である「万能チューリングマシン」を提示した。