人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

●質問者: kabisuke
●カテゴリ:コンピュータ 学習・教育
✍キーワード:Wikipedia チューリングマシン 勉強 帰着 教授
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● punkaholic
●100ポイント ベストアンサー

計算理論の基礎

計算理論の基礎

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

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

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

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

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

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

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

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

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

より具体的には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の元かどうか判定すればよい

ことになります.

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

◎質問者からの返答

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

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ