計算論に詳しい方に質問です。

チューリングマシンの判定可能問題を勉強していたのですが、
「EQ_CFG(文脈自由文法の等価性)は判定不可能」
という証明の仕方が分かりません。

「ALL_CFG(あるCFGの言語がΣ*であること)は判定不可能」
であることを利用すればそこに帰着させれば簡単に解けること、
ALL_CFGは、チューリングマシンのあらゆる計算過程を示す「計算履歴」と呼ばれる概念を用いれば証明可能であること、
あたりはWikipediaの文脈自由文法の欄を読んで理解しました。
しかし、チューリングマシンの計算履歴というのは何か、
そしてそれをどうすればALL_CFGの証明に生かせるのか
さっぱり分かりません。
どなたかご教授ください。

回答の条件
  • 1人2回まで
  • 登録:2008/01/14 20:36:29
  • 終了:2008/01/17 09:48:09

ベストアンサー

id:punkaholic No.1

punkaholic回答回数33ベストアンサー獲得回数112008/01/15 03:32:02

ポイント100pt

計算理論の基礎

計算理論の基礎

  • 作者: マイケル シプサ
  • 出版社/メーカー: 共立出版
  • メディア: 単行本

この本に詳細があります.自分の手元にある英語版からかいつまむと(蛇足ですが英語は第二版が出ているはず),

チューリングマシンの計算履歴とは何か?

これは文字通り,スタートからある時点までの計算の履歴です.まずwqauのような列(qは状態,w,uはΣ*の元, aはΣの元)をconfigurationと呼びます.これは,チューリングマシンの状態がqで,aを読んでいる状態を表します.configurationの有限列を「計算履歴」と呼びます.特にconfigurationの有限列C_1, C_2,..,C_kで

  • C_1=qw, qは初期状態,wは入力
  • C_iからC_{i+1}へは正しい遷移
  • C_k=wq', q'は受理状態

であるものをwに対する受理履歴と呼びます.

たとえば.q_1を開始状態で入力がabcだったとしたら,q_1abcから始まって,遷移関数がT(q_1,a)=q_2だったら,次はaq_2bcとなります(これが「正しい遷移」の意味です).最終的に終了状態q'に対してabcq'となっている履歴がabcに対する受理履歴となります.

どのようにALL_CFGの証明に活かすのか

一言で言うと「計算履歴は適当なアルファベット上の語である」ことを利用する,ということになります.上の例を続けると,上で挙げた履歴は

  • #q_1abc#aq_2bc#...#abcq'

のような語と見なせます(#は区切りのための文字).

より具体的にはA_TM={<M,w>| チューリングマシンMは入力wを受理する}(=決定不能)をALL_CFGに帰着させます.

チューリングマシンMと語wが与えられたときに,「Mのwに対する受理履歴ではない文字列すべて」を生成する文脈自由文法G_{M,w}をつくれることを示します.Mがwを受理しなければG_{M,w}の言語はΣ*となるので,<M,w>がA_TMの元かどうかを判定するには

  1. G_{M,w}をつくって
  2. G_{M,w}がALL_CFGの元かどうか判定すればよい

ことになります.

久しぶりにざっと眺めただけなので穴があるかもしれませんが,だいたいこんなところでしょうか.

id:kabisuke

なるほど、計算履歴とはそういうものだったのですか。

「G_{M,w}をつくって」のくだりがどうすればいいのか

よく分かりませんでしたが、回答にあった「計算理論の基礎」を読んで

理解することができました。

詳しい解説本当にありがとうございました。

2008/01/17 09:47:01

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません