チューリングマシンとは、1936年にイギリスの数学者アラン・チューリングが、「計算可能数についての決定問題への応用」で考案した仮想機械。
コンピュータや計算を数学的に議論するための道具であり、単純化・理想化された計算機モデルであると言える。

この仮想機械は、無限に長いテープと、その中に格納された情報を読み書きするヘッド、機械の内部状態を記憶するメモリで構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、下の動作を一つ実行する。

• ヘッドを右か左に一つ移動すること
• ヘッドの位置の情報を読みとること
• ヘッドの位置に情報を書き込むこと
• 機械の内部状態を変えること

チューリングは、数学の形式体系が全てこの仮想機械の有限回の動作に還元出来ること、すなわち一定の解法が存在する命題は全てこの仮想機械上で実行することが可能であることを示したが、しかし同時に、この機械が有限回で停止することができない命題が存在すること、そして、現在実行している問題が有限回で停止するかどうかを事前に判断することが不可能であることも証明した。(これはゲーデルが1931年に出した「ゲーデルの不完全性定理」の別表現になっている)

現在のコンピュータの基本的動作も、突き詰めて考えれば、このチューリングマシンの原理にしたがっていると言える。実用上のコンピュータはチューリングマシンよりも遥かに複雑であり、また有限の記憶領域（=テープ）しか持たないが、「現在のコンピュータで原理上計算できる問題」は「チューリングマシンが有限回で停止する問題」と同値である。