チューリングマシン

あらゆる計算を理論上表現できる、コンピュータの原理を説明するために考え出された数学的なモデル。

無限に長いテープと、そこに書かれた記号を読み書きしながら移動するヘッドという、非常にシンプルな仕組みだけで、理論上どんな計算も表現できることを示すために考案された概念上の機械。

現在のコンピュータが「何を計算できて、何を計算できないか」という限界を考える上での、理論的な出発点として位置づけられている。