まずは 6.1 再帰定理。このあたり、λ算法との関連性が高いような感じがする。関数という単語がたくさんでてくるし。シプサが終わったらλ算法も少し勉強したい。CLを勉強していて、lambdaとか出てくるんだけど、λ算法をさっぱり知らない、というのはどうもいけない気がする。
将来λ算法をやるときの接続ポイントになるかも、と意識しつつも、あくまでTuring機械の観点で理解すればよしとする。深掘りすると抜けられなくなりそうで。
※予告：この回、文章がかなりぐだぐだです。
- 「自分自身を再生産する機械を作ることは可能である。」
- これ、大事なので、原著もあたっておく。
- 「Making machines that reproduce themselves is possible.」
- まず、入力には関知しないで、とにかく自分自身の記述(のコピー)を出力するTMを作ることを目標にする。それをSELFと呼ぶ。
- その準備として次の補題を確認する。
- 「補題6.1
wを任意の文字列とすると、q(w)がwを出力して停止するTuring機械Pwの記述であるような計算可能な関数q:Σ*->Σ*が存在する。」
- この章に入ってから、ほにゃららなTMが存在する、ということを、ほにゃららな計算可能な関数が存在する、とかの言い回しをすることが多い。
- さて、まず計算可能な関数qがある、という。
- ということは、その計算を実行できるTM Qがある、ということ。
- qはΣ* -> Σ*。
- 入力文字列は任意。wとする。
- 出力文字列はとあるTMの表現。どんなTMかというと、入力文字列に関わらず、とにかくwをテープに書いちゃうようなTM。これをPwと呼ぶ。
- そうするとQは2つの部分にわけるとよさそうだ。
- Pwを構成する。
- 前項で構成したPwから表現をつくる。その表現を<Pw>と表記する。
- これは、できるのか??
- 考える便宜のためにマルチテープTMとする。
- まず、TM Qが動き出したとき、テープにはwが書かれている。それを読んでTM Qはwを知ることができる。
- 一般にTMの仕様は{Q,Σ,Γ,δ,q0,qaccept,qreject}で特定できる。これを文字列で表現するのは決めの問題だけ。TMはとにかく表現可能。
- Pwの仕様概要は、「入力文字列を消去して、wをテープに書いて受理」というだけ。
- 入力文字列の消去は、TMでできる。
- wを書くのはどうか?
- wが"01"だとして、計算状態でいうと、q__ -> 0r_ -> 01s というように状態と遷移関数を組めばいいだろう。
- よって、PwなるTMは存在する。
- なので、できる。
- 関数qってどんなものだろ、とイメージする。wが"01"だとしたとき、上のようにwを出力するTMの表現(<Pw>)がでてくるから、かなりけったいな文字列に写像する関数なのだろう。
- TM Qってどんなものだろ、とイメージする。これはテープに例えば"01"と書かれて動作開始すると、それを消去して前項のかなりけったいな文字列をテープに書き出して受理状態として終了するようなものだろう。
- さて、TM SELFを構成する。
- SELFは二つの部分から成るとする。それぞれをA,Bと呼ぶ。
- 最初にAが動作して、終了すると制御をBにうつし、Bが動作することにする。
- Aの仕事は、Bの記述を出力することとする。出力される表現を<B>と書く。
- Bの仕事は、Aの記述を出力することとする。出力される表現を<A>と書く。
- すると<A><B>と結合した文字列は、SELFを記述しきっているから、<SELF>と認定できる。
- なので、こういうAとBを構成できれば、SELFは構成できたことになる。
- AはPwをベースにする。
- Aは<B>という文字列をとにかく出力するものなのだから、AはPwのwを<B>にしたP<B>であるとしてしまう。(それなら間違いなく<B>を出力する)
- さて、上の関数qのイメージのところで"01"としたところを、<B>に読み替えてみる。
- qによって、入力<B>に対して、<B>を出力するTMの表現がでてくる。
- いいかえると、<A> = q(<B>) ということ。
- ただし、P<B>を構成するには、上でみたように、<B>を(Aを構築する際にすでに)知らなければいけない。
- では、Bはどうする。Bは具体的にTM的に構成して明示してあげなければいけない。
- まず具体的に構成できたとして、その構成の表現を<B>とする。
- そうするとそれはAの構成にビルドインされており、Aが動作すると<B>を出力する。
- ところでq(<B>) = <A>なのだから、BはAのこの出力を受け取って、Q的に動けばよいことがわかる。
- TM Bは次のとおり。
B = 「入力<M>に対して、(MはTMの一部の表現)
1. q(<M>)を計算する。
2. その結果を<M>と結合してTMの完全な記述をつくる。
3. その記述を印刷して停止する。」
- ミソは、やはりAとBの関係q(<B>) = <A>。
- さて、SELFが構成できた、ということはどういうことか。
- あるTM Mを表現するTM Sがあったとすると、TM SはTM Mのことをあらかじめしっていて、かつその構成の一部にTM Mを含んでいるので、TM SのほうがTM Mよりも複雑にならざるをえない、と思われる。
- たいていの場合はそうなのだが、SELFのように、「自分自身の構成のあり様」と「自分自身を表現する動作」ということが単体で充足している不思議な構造をもったTMも存在する、ということが言えたのだ。
- さて、ちょっと違う観点でみると、<SELF>をTMをシミュレートする万能TMのようなものに入力すると、<SELF>を出力する。
- これは、ここまで見てきたとおり、アプリオリではない。(print "I'm SELF")とかを考えてみれば、実感できる。
- では、万能TMにではなくて、人間に、同じような機能をもったプログラムというか指示というかその表現を与えるとしたらどんなものがあるだろう。
- それが、
この文を書き写せ。
であると。
- 「この」という自己参照を排除したバージョンは、
次の文を二つ書き写して、二つめの文を鉤括弧で囲め。
「次の文を二つ書き写して、二つめの文を鉤括弧で囲め。」
ということ。
- SELFがわかったところで、再帰定理。
- 「再帰定理(Recursion Theorem)
Tを、関数t:Σ*xΣ*->Σ*を計算するTMとする。このとき、すべてのwに対して、
r(w) = t(<R>, w)
となる関数r:Σ*->Σ*を計算するTM R が存在する。」
- 再帰定理の説明がわからない。ちょっとわからなさすぎる。日本語としてもわかりにくい。
- 原著を読む。
- う、この部分は翻訳より原著の方がはるかにわかりやすい。
- 自分なりにわかりやすく訳す。(再帰定理の説明のところ。P262)
- 「この定理は多少ややこしくみえるかもしれないが、実はとても簡単なことを言っているにすぎない。どういうことかというと、自分自身の表現をテープに書き出せたりそれを計算に利用できたりするようなTuring機械を構成するには、この定理にあるようなTuring機械 T を構成すればよい、ということだ。T は 入力文字列wに加えて、Turing機械の表現も入力として受け取るようにしておく。そんなTに対応して、入力文字列wに対する動作がTと同じであるTuring機械 R が存在しますよ、そしてそのときR自身の表現が(Tへの入力の一方として)内包されていますよ、というのが再帰定理が述べるところである。」
- このまま訳書で進めていくべきかどうか迷った。ここの説明、誤訳ではないが、私には理解できない日本語だ。。。
- せっかくここまで来たから訳書を完全にすてるのではなく、原書と両用していくことで対処することにする。
- 再帰定理の証明は簡単。
- 気になるのは、再帰定理が、T -> R という流れということ。一般的に利用したいのは、R -> T という事実なような気がする。
- t:Σ*xΣ* -> Σ*、 r:Σ* -> Σ*なので、再帰定理がなりたつなら、Rに対して、Tも存在しそう(構成できそう)なので、ここはスルーする。
- 再帰定理を認めてしまえば、残りの話は簡単だった。
- 再帰定理を用いた、A[TM]の判定不可能性の証明。
- 再帰定理を用いた、MIN[TM]の認識不可能性の証明。
- 再帰定理を用いた、TMを変換するような計算可能な関数に対する不動点TMの存在証明
- こうしてみると、TMというのは、その仕様によって、
- TMの表現を受け取ってそれをシミュレートできること。
- 自身の表現を得ることができること。
の2つが成立していて、これらがTMの特質として支配的であり、他の定理を導きやすいような気がする。
ああ、こつこつじゃなくて、ぐだぐだ。
次回は、「6.2 数理論理における判定可能性」。ここは「論理学をつくる」との接続ポイントになるかも、なので楽しみ。
