チューリング機械とは、1936年に発明された単純な機械で、世の中で計算と言われるどんな計算も出来るというもの。人によっては人間の知性自体も計算だ！なんて言い出す人もいるから、もしもそれが本当だとしたら、僕たちが日々嘆いたり喜んだりしている事も単純な機械の組み合わせに過ぎない事になってしまう。とにかくチューリング機械とは、世の中のどんな複雑な仕組みも、実現可能なすごいマシンなのだ。http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
ここで実現可能というのは普通の言い方と違うので雰囲気で説明すると、例えばあなたの体が小さな細胞の集まりで出来ているように、「計算」も小さくて単純な計算の集まりで出来ているとすれば、その一番小さな計算ってどんなだろう。その一つの提案がチューリング機械だったわけ。僕たちの頭の中にある「考え」もやっぱり想像上の原子で出来ていて、それが単純な機械でも同じ事が出来るというのが分かったら何だかロマンチックでしょう。
チューリング機械の目的は、考えの原子みたいなものを作るのが可能だと証明する事だったから、割とその細部は複雑なままほったらかしなんだけど、世の中にはしつこい人が大勢いて、もっとすごい単純なチューリング機械を考えてやろうと 1950 年代から 60 年代にかけて相当盛り上がりがあったらしい。色んな人が「俺チューリング機械」を沢山考えた。だけどその盛り上がりの後、Allen Brady は John McCarthy との会話の中で、
- 「もしも最小の万能機械を発見できたら、計算科学にとってすごい事だと思ってたんだけど、そんなわけ無かったよ」
と言ったという。また、Marvin Minsky が言うには、
- 「諸君もこの競争(世界最小万能機械発見競争)に挑戦してみると良い。しかしながらこの競争が強烈トリッキーなパズルで、そのくせ数学的価値が皆無である事を心すべし」
まあそんなわけで熱狂は去ったわけだけど、それでもこの種の問題はやはり勉強のためや、ただ楽しみのためには大きな意味がある。特に Brainfuck に代表される難解言語コミュニティでは、特に「強烈トリッキーなパズル」な所が魅力にもなっているらしい。「チューリングの泥沼(Turing tarpit)という言葉自体は、1982 年の『プログラミングの警句』で Alan Perlis が語った言葉から来ている。
- 「チューリングの泥沼に注意せよ。それは何事も可能であり、何事も容易に非ず。」
