チューリングマシン語り 後半

http://metanest.jp/tm/tm.xhtml にまとめました

id:metanest:20070424#turing の続き

停止問題

あるチューリング機械についてテープに記述すること、あるいはその記述を入力として受け取るようなチューリング機械が存在することから、次の議論を始めることができる
「あるチューリング機械に、ある入力を与えた時、停止するかしないかを判定するチューリング機械は可能か？」
これが「チューリング機械の停止問題」である
答えは「否、存在しない」で、おおざっぱに説明すると以下のようになる
（疑似言語として 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)  # ???

• t(t) が停止すると仮定 → terminate? の定義により true が返る → 無限ループで停止しない
• t(t) が停止しないと仮定 → terminate? の定義により false が返る → 停止する

という矛盾する結果が導き出される。よって、(1) のような terminate? は存在しない //

チューリング完全

チューリング機械で、なんであれシミュレーションできる、ということから、例えばプログラミング言語において、任意のチューリング機械を記述できる能力があれば、なんであれ記述できる、ということになる
（その結果がわかりやすいか、効率的か、といった点を無視すれば。また、無限の長さのテープについては、適当な長さでよいとする）
そのような「任意のチューリング機械（万能チューリング機械、と言い替えることもできる）を記述できる能力がある」ことを、「チューリング完全」という
どれくらい単純なプリミティブで、チューリング完全を達成できるか、という問題が注目された時期もあった
http://esoteric.voxelperfect.net/wiki/Turing_tarpit
また、現代でも、何らかのメカニズムがチューリング完全か否かという問題は時に面白い議論となる

参考文献他

• 「ファインマン計算機科学」第３章　計算の理論

ファインマン計算機科学

物理学者ファインマンさんによる計算機科学の教科書
「計算可能性」の導入からはじまり、有限状態機械、チューリング機械、万能チューリング機械、停止問題が説明され、最後に計算可能性に関わる問題が提示されている
ミンスキーさんによる万能チューリング機械が示されている

• 岩波講座 情報科学 14「計算機の機能と構造」第 11 章　理論上の計算機

NACSIS Webcat BN00375778
古い教科書だが、大学の図書館などにはあると思う
チューリング機械についての紹介。高橋秀俊さんによる万能チューリング機械が示されている

• 「計算理論とオートマトン言語理論」

（未確認）

計算理論とオートマトン言語理論―コンピュータの原理を明かす (Information & Computing)

目次 http://www.saiensu.co.jp/?page=book_details&ISBN=ISBN978-4-7819-1104-5 によると万能チューリング機械の解説がある模様

• 中公新書「数理パズル」

コンウェイさんのライフゲームで、万能チューリングマシンが実現可能との記述があったように思うのだけれど手元に無くて確認できず...

• 「ライフゲイムの宇宙」

ライフゲイムの宇宙

これも手元になくて確認できないのだけど、チューリング完全に関する話がもしかしたらあったかも

• 「ゲーデル・エッシャー・バッハ」

（非参考文献）

ゲーデル,エッシャー,バッハ―あるいは不思議の環

ゲーデル、エッシャー、バッハ―あるいは不思議の環 20周年記念版

長門有希も読んでた本書には、まさしくこの分厚い中のどこかにありそうなテーマであるにもかかわらず、万能チューリング機械についての直接の説明は見つからず（索引に「チューリング・マシン」はあるが、「万能――」はなく、関係のありそうな語のあたりをいくつか探してみるもありませんでした）。停止問題は関数で説明されている