チューリング機械

ちゅーりんぐきかい

テープに記号を読み書きするだけの、ごく単純な仮想の機械。「計算できる」とはどういうことかを定義するために、1936年にチューリングが考えた。

機械は、長いテープの1マスを読み、決められた規則に従って記号を書き換え、テープを1マス動かす、という動作を繰り返すだけです。チューリングは、人が手順を踏んで計算できることはすべてこの機械でできると論じ、同時に、どんな機械にも答えの出せない問題があることも証明しました^[1]。

さらに、規則そのものをテープに書いておけば、ほかのどんなチューリング機械のまねもできる1台(万能機械)が作れることを示しました。計算ごとに別の機械を作らなくてよい、という保証です。1台のコンピュータがプログラムを入れ替えるだけで何でもこなせるのは、この結論の上に立っています。