＞トップ
本稿は http://d.hatena.ne.jp/metanest/20070424#turing と http://d.hatena.ne.jp/metanest/20070425#turing に書いたものを固定コンテンツとしてまとめたものである．敬称の省略，情報の追加等をおこなっている
前世紀の前半において数学上重要だった話題に「そもそも計算とは何ぞや」という問題がある。そこでチューリングが考案し 1936 年に提示した、単純にして万能な計算機械が「チューリング機械」である
数学的に議論するための、単純化・理想化された仮想機械である。(ウィキペディアより)
ここでいう、チューリング機械の万能性は、あとで出てくる「万能チューリング機械」と、かかわりは深いのだが、あくまでも別の概念であることに注意が必要である
ウィキペディアの「現実の計算との関係」にあるように、あらゆる計算する機械、さらにはあらゆる形式的な数学の体系を、チューリング機械の動作に還元できる、ということが、ここでの「万能」の意味である
ウィキペディアのチャーチ=チューリングのテーゼのあたりも参照のこと
戦後のことになるが、チューリングは、人間の脳を計算機でシミュレートする可能性について論ずることとなる。そのとき、まさにそのとき、どんな複雑な計算機械であっても、それをある計算機械で「真似ることができるという性質」によって、計算機の能力を想像の彼方まで見積もることを正当化しているのである
田中求之さんによる「チューリング・テスト再考」 http://mtlab.ecn.fpu.ac.jp/myNote/reconsidering_turing_test.html の ５節 Universarity of Digital Computer のところにある
いわゆる「ノイマン型」、プロセッサと書き換え可能なメモリからなり、データとプログラムが同一視されるモデルは、メモリが十分であると仮定すればチューリング機械と同等の能力を持つ機械の実現と考えられる。そのような観点から、コンピュータの歴史上最初に実用的に実現したとされる EDSAC を重要視することがある
あらゆる機械を真似ることができるなら、チューリング機械を真似るチューリング機械はどうだろうか？
ここで、次のようなチューリング機械を考えてみる
このようなチューリング機械があれば、あらゆるチューリング機械の動作を真似ることができるわけである。そのような機械こそが「万能チューリング機械」である
チューリング自身によって示された万能チューリング機械は複雑なものであったが、単純化が流行った時期があるようである。しかしながら「面白い問題であるが，深い重要性はない．」（「ファインマン計算機科学」 pp. 64〜65 ）
あるチューリング機械についてテープに記述すること、あるいはその記述を入力として受け取るようなチューリング機械が存在することから、次の議論を始めることができる
「あるチューリング機械に、ある入力を与えた時、停止するかしないかを判定するチューリング機械は可能か？」
これが「チューリング機械の停止問題」である
答えは「否、存在しない」で、おおざっぱに説明すると以下のようになる
（疑似言語として Ruby 風の表記を使っていますが Ruby ではありませんので注意）
(1) 仮に、そのような機械が存在するとする。すなわち、機械の記述を m、その機械への入力を i として、以下のような関数 terminate? が存在するとする
terminate?(m, i) # m(i) が停止するならば true 、しないならば false を返す
(2) この terminate? を使った、以下のような関数 t を考える
def t(x)
if terminate?(x, x) then
loop {} # 無限ループ
else
stop # 停止
end
end
(3) この t に t 自身を入力として与えた場合を考えてみる
t(t) # ???
という矛盾する結果が導き出される。よって、(1) のような terminate? は存在しない //
チューリング機械で、なんであれシミュレーションできる、ということから、例えばプログラミング言語において、任意のチューリング機械を記述できる能力があれば、なんであれ記述できる、ということになる
（その結果がわかりやすいか、効率的か、といった点を無視すれば。また、無限の長さのテープについては、実際の場合には適当な長さでよいとする）
そのような「任意のチューリング機械（万能チューリング機械、と言い替えることもできる）を記述できる能力がある」ことを、「チューリング完全」という
どれくらい単純なプリミティブで、チューリング完全を達成できるか、という問題が注目された時期もあった http://esoteric.voxelperfect.net/wiki/Turing_tarpit
また、現代でも、何らかのメカニズムがチューリング完全か否かという問題は時に面白い議論となる
「2, 3 チューリング機械」という単純な機械がチューリング完全かどうか、という問題がウルフラムによって懸賞問題となっていたが、肯定的に解決された
物理学者ファインマンによる計算機科学の教科書
ミンスキー（「人工知能の父」）による万能チューリング機械が示されている
古い教科書だが、大学の図書館などにはあると思う
チューリング機械についての紹介。高橋秀俊先生による万能チューリング機械が示されている
（未確認）目次 http://www.saiensu.co.jp/?page=book_details&ISBN=ISBN978-4-7819-1104-5 によると万能チューリング機械の解説がある模様
コンウェイのライフゲームで、万能チューリングマシンが実現可能との記述があった。と思う
自己再製するパターンを作るためのツールとして、万能機械のはたらきをするパターンが可能であることが説明される（コンウェイはこれを証明している）。12 章 1 節〜 5 節
（非参考文献）
長門有希も読んでた本書には、まさしくこの分厚い中のどこかにありそうなテーマであるにもかかわらず、万能チューリング機械についての直接の説明は見つからず（索引に「チューリング・マシン」はあるが、「万能――」はなく、関係のありそうな語のあたりをいくつか探してみるもありませんでした）。停止問題は関数で説明されている