1.ポスト対応問題 (1)文脈自由言語k=4の例 ポスト対応問題のインスタンスをなんとなく(110,01),(10,0)(001,111),(1,11)とおく。すると、L(x1,x2,x3,x4)={1#10#11#100#110001011} になる。これより、文脈自由文法は S→ij# S xijR S→ε (2)2つの文脈自由文法が…

1.1テープと2テープのTMの性能差 言語{0^n1^n} 2テープ：O(n) 1テープ：O(nlogn) 言語{xcxR} 2テープ：O(n) 1テープ：O(n^2) 教科書にあったの。 説明は直感的でいいみたいなので、交差列の説明とかはいらんかな？？？ 2.空集合問題の非可解性 教科書どおり…

明日テストなので、過去問を解いてみる。ムズすぎる。 間違いだらけやと思うので、おかしいとこは教えてください。＞＜ 1.言語{0^n1^m | n制限なしのポスト対応問題のインスタンスすべての頭にa(決まった記号)をつけるという還元を作る。 制限なしのポスト対…

非可解性の証明や、NP完全性の証明をするときには、 すでに非可解であったり、NP完全であると証明されている問題のインスタンスを 証明したい問題のインスタンスに還元することで証明をする。 これがなんとも分かりにくいので、 解きたい問題とインスタンス…

改訂版：TMの停止問題は非可解であることの証明。 旧版がカオスになったので書き直す。TM停止問題 - hat-tunの日記 L={ρi| TMρiは列ρiに対して停止して受理しない} という言語が必ず停止するTMで認識できないことは証明されているとする。 まず問題を分析す…

TMの停止問題は非可解であることの証明。 L={ρi| TMρiは列ρiに対して停止して受理しない} という言語が必ず停止するTMで認識できないことは証明されているとする。 まず問題を分析する。 TM停止問題が非可解 インスタンスとしてTM Mと列ρ。 Mがρに対して停止…