これも情報工学で習う難物です。チューリングマシンとは1936年にアラン・チューリング（Alan Mathison Turing，1912-54）が考えた仮想のオートマトンで、コンピュータの動作を究極まで単純化したものといえます。
　チューリングマシンは、等間隔に区切られた無限に長いテープと、そのテープに読み書きするヘッドからできています。ヘッドは｢状態｣をもっていて、テープから読み取ったデータに応じて｢状態｣を変えます。チューリングマシンのすることは、／ヘッドを右か左に一区画移動する ／ヘッドの位置のデータを読む／ヘッドの位置にデータを書き込む／｢状態｣を変える／だけです。これで何ができるの？と思ってしまいますが、コンピュータにできることはすべてできるのです。

　1936年といえばコンピュータが実現する10年も前です。テープを使ったのは、他に適当な記憶装置がなかったからでしょう。これは現在のコンピュータで言えばメモリーに相当します。そしてヘッドがCPUに相当します。
　なぜこんな難解なものを考えたの？と思ってしまいますね。計算という行為を抽象化していくとこんなものになって、本質が浮かび上がってくるということです。それは数学の面白いところでもあり、嫌われるところでもあるわけです。　　--- Y.O. ---