- 6.1 再帰定理の考え方を利用して、自己複製プログラムをつくれということ。
- 問題の解釈はいろいろあるが、とりあえず、CLということで、REPLにて評価の前後で形がかわらないS式をつくる、というお題とした。
- また、TMへの入力を関数の引数とした。よってTMが各部にわかれている場合、各部の間の入力出力の組み合わせは、関数の連続適用によってなされているとした。
- 一番簡単なのは、NILなんだが、それはおいといて。
- こんな感じ。
((lambda (B)
`(,B ((lambda () ',B))))
((lambda () '(lambda (B)
`(,B ((lambda () ',B))))))) - quoteをちゃんと書くと、こんな感じ。
((lambda (B)
(list B (list (list (quote lambda) nil (list (quote quote) B)))))
((lambda () (quote (lambda (B)
(list B (list (list (quote lambda) nil (list (quote quote) B))))))))) - 後々、C言語でもやってみたい。今はやらない。
- 問題の解釈はいろいろあるが、とりあえず、CLということで、REPLにて評価の前後で形がかわらないS式をつくる、というお題とした。
- 6.2 「MIN[TM]の任意の無限部分集合がTuring認識可能でないことを示せ」
- えっとMIN[TM]って何だっけ。
- TMの表現を集めた言語。
- ただし、それはそれぞれのTMにおいて文字列長において最小のもののみ有資格。
- TMの表現を集めた言語。
- で、これは認識不可能だったはずだがなぜか。
- 再帰定理がきいてくる。
- えっと、まずMIN[TM]を認識するTM Mが存在するとする。
- するとMを変形してMIN[TM]の列挙装置もつくれる。これをM'とする。
- 次のようなTM Sを構成する。
- 入力をwとする。
- まず、再帰定理で自分自身の表現<S>を得る。
- 列挙装置M'を動かして、<S>より長いTM表現を得る。これを<T>と呼ぶ。
※証明はしていないが、TMの定義からいって、Tが常に存在することは問題なさそうだ。 - <%>を入力wについてシミュレートする。
- 入力をwとする。
- すると、TM SはTM Tと同じ動作をするTMである。
- ここで、TM Sの中では、<S> < <T>が長いということになっている。
- これは、列挙装置M'が出力するTMの表現が「同種のもので最小である」といことに反している。ゆえに仮定がおかしい。■
- 再帰定理がきいてくる。
- えっと、この証明をそのまま「MIN[TM]の任意の無限部分集合」に適用すればよいかと。■
- えっとMIN[TM]って何だっけ。
- 6.3 「A <=T B かつ B <=T C のとき、A <=T C であることを示せ」
- A <=T B の定義はなんだっけ?
- たしか、Aのoracleが存在した場合に、Bが判定可能となるようなAのoracleをつかった手順が存在すること、だった。
- たしか、Aのoracleが存在した場合に、Bが判定可能となるようなAのoracleをつかった手順が存在すること、だった。
- えっと、記法をさだめる。
- AのoracleをOR[A]とかく。
- oracle OR[X]を使った判定手順をT[OR[X]]とかく。
- AのoracleをOR[A]とかく。
- すると、T[OR[A]]はBを判定し、T[OR[B]]はCを判定する、ということ。
- このとき、T[OR[A]はBを判定するのだから、Bのoracleでもある。Cについてもしかり。
- Cのoracle = T[OR[B]] = T[OR[T[OR[A]]]]]。
- これはAのoracleが存在すれば、それを使った手順にてCのoracleが作れる、すなわちCを判定できることを示している。
- この言明は、A <=T Cの定義そのもの。■
- A <=T B の定義はなんだっけ?
- 6.4
- A[TM]ってなんだっけ?
- A[TM] = {<M,w> | TM Mは入力wを受理する。}
- では、A[TM]'って何だろう? 問題文からすると
- A[TM]' = {<N,x> | Nはoracle TMである。A[TM]に対するoracleを内蔵したoracle TM M^(A[TM])はxを受理する}
- ということ? ちょっとよくわからない。
- しょうがないので、A[TM]'を自分なりに組み立てて探る。
- まず、MというTMがある。これはTMの定義にしたがって仕様がきまる。
- TM Mはいろいろな入力にたいして、受理したり拒否したりループしたりする。
- 言語A[TM]というのは、そんなTMと入力の組み<M,w>について、受理するものだけの表現を集めたものということだった。
- さて、言語A[TM]に対するoracleというのは、任意の文字列について、それがA[TM]の要素かどうかを判定してくれる超機械であった。
- その超機械への問い合わせ機構をもった特殊なTMをoracle TMと呼び、oracleというのは言語に紐づいて設定される概念であるから、その名前をM^(A[TM])などと、言語とともに書くことにした。
- M^(A[TM])は、A[TM]を判定するoracle TMである。よってその入力は、A[TM]の要素<M,w>である。
- さて、A[TM]は、TMと入力の組だった。この考えをoracle TMに拡張できるか。
- A[TM]'はoracle TMと入力の組。ただし、入力はまったく任意ではなくて、M^(A[TM])が受理するものに限るとする。
- この組の数は膨大になるかもしれない。なぜなら、oracle TM が入力を受理する、などの制限をかけていないので、すべてのoracle TMの表現がこの言語に含まれるからだ。
- さて、これがA[TM]'の理解として正しいのかどうか微妙だが、正しいとして解答をこころみる。
- まず、A[TM]'がA[TM]に対して相対的に判定可能だと仮定する。
- ということは、M^(A[TM])を使ってA[TM]'を判定する手順が存在する、ということ。
- 。。。いきづまった?
- 問題の解釈に間違いがあるか?
- 「さて、A[TM]は、TMと入力の組だった。この考えをoracle TMに拡張できるか。」というところを、oracle TM M^(A[TM])としてみる。
- するとA[TM]'はあくまで受理される組についての言語になり、すこしまっとうになった気がする。
- さて、これがA[TM]'の理解として正しいのかどうかひきつづき微妙だが、正しいとして解答をこころみる。
- まず、A[TM]'がA[TM]に対して相対的に判定可能だと仮定する。
- ということは、M^(A[TM])を使ってA[TM]'を判定する手順が存在する、ということ。
- あ、これは簡単に判定できる。wをM^(A[TM])にくわせるだけじゃん。
- うむー。問題文を理解できないとつらい。これは未来の自分への課題として、先へ進む。
- A[TM]ってなんだっけ?
- 6.5
- ∃x∀y [ x+y=y ]はTh(N,+)の要素である。
- なぜかというと、x=0∈Nとするとき、関係0+y=yはyの値に関わらずtrueとなる。よって、この言明はtrueであり、Th(N,+)の要素となる。
- ∃x∀y [ x+y=x ]はTh(N,+)の要素ではない。
- なぜなら、例えば、y=1∈Nにたいしてxは存在しない。よってこの言明はfalseである。falseな言明は、Th(N,+)の要素ではない。
- ∃x∀y [ x+y=y ]はTh(N,+)の要素である。
- 6.3と6.5の解答を確認。芯は外していないな。
6.4の問題文を理解できなかったのがくやしいが、一応シプサの第二巻を読了した！！
次回から第三巻 複雑さの理論。
まずは第7章 時間の複雑さ。ここはbig-Oだとかsmall-oだとか、NP完全だとか、これまたいろんなところでよくみるけれど、全然知らなくて、いつも理解を妨げていた概念たちだ。楽しみ。
0 件のコメント:
コメントを投稿