GEBを読む→(ﾟДﾟ)ｳﾏｰ

　≪これからも「相違の中の同一性」、そして「二つのものは、どんなときに同じといえるのか？」という問いを目指して走りつづけることにしよう。この問いは本書の中で繰り返し論じられる。
われわれはこの問いをあらゆる角度からとりあげ、最後には、この単純な問いが知性の本質にいかに深くかかわっているかがわかるであろう。≫(p.162)

　GEBのテーマは、再帰です。そして、再帰はG・E・Bの三者にとってもテーマでした。


　というわけで、不朽の名著『ゲーデル・エッシャー・バッハ』（D・ホフスタッター　白揚社）を読むスレです。僕も勉強しながら（要するに見切り発車）の書き込みなので、多々間違いがあると思います。
批判・意見は遠慮なくお願いします。ま、700ページ超だし、気長に行こう。

テーマ：
　再帰手続きを使うゲームで、再帰というものを実感する。その上で、システムの内と外の区別、再帰によって生成された≪定理≫の集合が≪木≫構造をなすこと、再帰と木は相性が良いことを理解する。

　≪あなたはMUをつくれるか？≫

　まず、再帰手続きを自分の手で実行する目的で、MIUシステムが導入される。一つの公理と4つの導出規則。簡単極まる公理系です。その公理と規則は以下の通り。

　公理：最初の持ち物はMIのみ。

　規則１：持っている文字列の最後の文字がIなら、その後にUを付けてよい。
　規則２：文字列Mxを持っているなら、Mxxを持ち物に加えてよい。
　規則３：持っている文字列にIIIが含まれていたら、それをUで置き換えてよい。
　規則４：持っている文字列がUUを含むなら、それを省略してよい。

　
　さて、この約束に従って、いくつか文字列を作ってみる。例えば、
　　(1)MI 公理
　　(2)MII (1)から規則2
　 (3)MIIII (2)から規則2
　　(4)MIIIIU (3)から規則1
(5)MUIU (4)から規則3

　こうして、持ち物の文字列が増えていく。新しく≪生成≫された（証明された、という言葉とは一応区別されてる）文字列は≪定理≫と呼ばれる。定理は、このMIUシステムという王国の国民です。

　≪MUパズルにとりかかる人はたいてい、どんなことが起るのかちょっと見るために、全く無作為にいくつかの定理を証明してみるものである。するとすぐに、得られた定理のいくつかの性質が発見できる。ここに人間の知能が登場する。≫(p.53)

　たとえば、全ての定理がMから始まることがわかる。最初の文字は、4つの導出規則のいずれからも影響を受けないからです。この知見こそが、人間と機械の一つの違いである、とホフスタッターは言う。つまり、

　≪機械が観察力なしに振舞うことは可能だが、人間が観察力なしに振舞うことは不可能だ。≫

　人間はシステムに「ついて」考えることができるが、機械にはできない。だから、MIUシステムの定理を次々と生成するプログラムを組むのは簡単にできる。
また、Uが生成されたときだけ停止するようそのプログラムを細工することもできる。そして、そのプログラムは決して停止しない。
　≪しかし、もし友人に、Uを生成してみてくれ、と頼んだらどうなるだろうか？･･････最初のMは消せないから、Uを作ることなど野生のガチョウを追いかけるようなものだ、とこぼしても、別に驚きはしないだろう。≫

　形式システムを扱う3つの方式が分類されます。3つ？2つしか出てきてないじゃないか、と思われるかもしれませんが、最後の一つは後の章で取上げられます。ここではとりあえず名前だけ。

M方式（Mechanical mode) ：システムの中で仕事をする
I方式（Intelligent mode)：システムについて観察する。
Un方式（Un-mode）：禅

　MUはMIUシステム内の定理だろうか？Mで始まる文字列でも、非定理の文字列は無数にある。MUもそのうちの一つかもしれない。どうにかして、MUが定理か非定理かを判別する検定法をみつけられないだろうか。
　さらに、MUに限らず、どんな文字列に対してでも適用できる検定法はないだろうか。ここで、一つの「ばかばかしい」検定法が提案される。

≪問題の文字列が生成されるまで待て。もし生成されるなら、それは定理である。もし永久に生成されなければ、定理ではない。≫(p.57)

　これは確かに、ある意味、馬鹿馬鹿しい。いつ答が得られるか見当がつかないから。せめて答は死ぬまでに得られないと、いくら正しい答でも困ってしまう。
もし定理性を検定する、いつでも有限時間で終る方法があるときには、その方法はその形式システムにおける≪決定手続き≫と呼ばれる。
　しかし、とにかくどんな文字列をも対象にできる検定法であることには違いない。この検定法で活躍するのが、≪木≫構造です。
p.57の第11図を見れば一目瞭然、MIU内部で生成される全ての定理は、≪木≫として網羅的に書き出すことができる（網羅的に、というところがポイント）。木は再帰的構造なのです。

　第1章は以上。さて、明日も労働しなければ。

　あ、一つパラグラフを抜かしました。次のレスを「システムの内と外」と「M方式、I方式、U方式」の間に入れて読んでください。

　先の「システムの内と外」をネタにした余談のパラグラフです。「機械はシステムの外に出られない」という主張が繰り返されます。具体例として、「途中で勝負を投げるチェスマシーン」が挙げられている。
もしシステムを「チェスのゲーム」と考えるならこのプログラムはシステムから脱出したと言える。しかし、システムを「コンピュータが実行するようプログラムされた全て」と考えれば、やはりこのチェスマシーンは外へ出る力を持たない。

　≪形式システムについて考えるときは、次の点が特に重要である。それはシステムの“中で”仕事をすることと、システムに“ついて”表現や観察を行なうことを区別することである。≫

　さて、コメントする箇所は幾つか考えられるけど、まず、
　　１．システムの意味について
　　２．決定手続き
　の二つが、僕だけでなく気になるところでしょう。

　１．について言えば、「１＋１＝２」という数学システムの中の文字列は意味を持つと思われるのに、MIUシステム内の文字列は全く無意味にしか見えない。
一体、あるシステムの意味は、どこからやってくるのだろう？この素朴な疑問は、しかし重要です。ホフスタッターも、すぐ次の章でこの問題を取上げます。

　２．は、名前こそ出てこないけど、多分チューリングマシンの停止問題です。TMの記憶装置は一次元テープなので、木構造ではないのですが、木のノード（要素）をテープに書き並べれば同じことです。
とにかく、どんなに長い文字列でも受理できるぐらいの“無限”の記憶領域を持つ、というところが重要。「停止するまでに時間はどれだけかかるかは問わない」というところもTMと同ですね。

また夜に。

今気づいたけど、MIUシステムって別に再帰じゃないですね。
しょっぱなからやってしまった。

３．証明と生成

　3つ目の着眼点として、この二つの概念の違い、というのも考えられる。ホフスタッターも一応二つを区別して使ってます。
　
生成―構成主義
証明―実在主義

　どちらを取るか、態度の違いぐらいしかないでしょう。文字列を生成する、という態度を取るとき、自分が実際に手を動かして生成するまでは、文字列は存在しないことになる（生まれてないのだから当然）。
僕が「MIUIUIU」という定理を書き出したとき、初めてこの定理はMIUシステムの王国に生を受けたことになる。可能無限的な態度、といってもいいかもしれない。MIUシステム内の定理の集合は、無限集合
には違いないから。

　逆に、「MIUIUIUが定理であることを証明せよ」と言われたらどうするか。何のことはない。結局僕は公理と導出規則を使ってシラミツブシに定理を書き出していくしかない（あるいは、MIUIUIUを出発点にして
遡るように定理を書き出してもいい。うまく公理MIに辿り着けばゴールです）。
　結局どちらの考えに立つにしても、実際に手を動かすレベルで見ればやることに変わりはないと思う。だからまあ、直接無限集合を対象にした議論でなければ、「心のもちよう」程度の違い、という気がします。

　うーんGEB読んでる人いないのかなあ。面白いのに。
　ま、もうちょいsageで続けてみるか。スレッド一個ぐらい貰ってもバチは当たるめえ。

　第2章のテーマ：
　　ある文字列の意味は、写像理論によって与えられる。
　　写像理論は、当然『論考』の写像理論です。ホフスタッターはWの名前は出さないし、写像理論という言葉も出さない（代わりに集合論の≪同型対応≫という言葉を使う）。
　　でも、どう読んでも僕には写像理論にしか読めないのだからしょうがない。

　第1章のMIUシステムとよく似た、しかしもっと簡単な形式システム「PQシステム」が導入される。
PQシステムには無限個の公理があるため、MIUシステムみたいに公理を直接書くことはできない。そこで≪公理図式(axiom schema)≫という書き方をする。

　公理図式：xがハイフンだけの列であるとき、xp-qx-は公理である。
たとえば、--p-q---は公理となる。xは全く同じハイフン列ということに注意しよう。

　導出規則：ハイフン列x,y,zについて、xpyqzが定理であれば、xpy-qz-も定理である。
　　　　　　例えば、--p---q-が定理なら、--p----q--も定理である。
　
　さて、このPQシステムには、≪決定手続き≫は存在するだろうか？つまり、ある文字列が与えられたとき、その文字列がPQシステムの定理であるか否かを判定する方法があるだろうか？
　次のパラグラフで、この問題に対する答と解説が行なわれる。実は、この問題の解説はひどく簡単。でも僕は自分では答えられなかった。というか、すぐ次を読んでしまった。

age
なんとなく昨日立ち読みしてパラパラとページ開いてたら
なんかウィトっぽさが散見された感じがする。なんとなく…。

同型対応が意味を引き起こすとか言ってた感じがするんね。
５５００円なんて買えるかっ！っての。

あげてみる

　久々に進めてみようか。

>>16
　古本でよければ、スーパー源氏なら2000円ぐらいで売ってるよ。

GEB、半分まで取り合えず読みました。
「押し込み」っていう所がよく理解できなかったよう。

ミックﾀﾝ進めてちょ

>>19

もし良かったらどこかの章まとめてください。

「押し込み」は第5章ですか？うーん、この章簡単だから端折るつもりでいたのだけど、どこが難しかったのだろう。いきなりコンピュータ用語が出てきたのが腑に落ちなかったんでしょうか。
「プッシュ」「ポップ」という動作と、「スタック」というデータ構造は、プログラミングの世界ではもう基礎中の基礎で最初に習う概念です。
記憶構造の種類には、ほかにキュー、ヒープなんかもあるけど、スタックの特徴はLIFO型であること。ラスト・イン・ファスト・アウト。つまり、最後にプッシュされたデータが最初にポップされる。
スタックは、その性質ゆえに、推論プログラムでよく使われる。例えば、ある前提を立てて次々に定理を格納していく。
しかしどこかで破綻が生じたために、最初の前提を変える必要が出たとする。そうすると最初の前提まで後戻りしなきゃいけなくなる。そのとき、最後に入れた定理から順に時間を遡ってポップしていくことになる。

ちょっとはイメージ湧きましたか？

　　　　　　　　　 ,,.-‐''""""'''ー-.､
　　　　　　　　,ｨ"　　　　　　　　　 ＼
　　　　 　 　 /　　　　　　　　　 　 　 `､
　　　　　 　 ,i　　　　　　　　　　　　　　i
　　　　　　r'-=ﾆ;'_ー-､___,,.ｨ‐‐-,,_　　__|
　　　　 　 | r,i　　　~`'ー-l;l : : : `l-r'"ﾒ､
　　　　　　ヾ､　　　　　　　`ー‐'": i!_,l_ノ`
　　　　　　　|　　　　　　　　 ,:(,..､ ;:|/
　　　　　　　|　　　　　　　　,,,..;:;:;:;,/ 　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　 /　　`::;;.　　　'"`ﾆ二ｿ　　　　　＜　 このスレはクソだなﾑﾈｦ！
　　　　　/7　　　　ﾞﾞ:`-､;:;:;;;:;:;:;;/ 　　　　　　　＼＿＿＿＿＿＿＿＿＿＿＿＿
　　　,,.ィ"`:､　　　　　　　　"/;:`ｰ-:､.._
　‐'":;:;:;:;:;:;:;:＼　　　. : :;: .　 ;/;:;:;:;:;:;:;:;:;:~`'''ー--:､,,_
　:;:;:;:;:;:;:;:;:;:;:;:;:;:`:､　　　　 .;;;/:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:~i!
　:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:`ー-''"":;:;:;:;:;:;:;:;:;:;:;:;:;:;:;:;;;:;:;:;:;:;:;:;:;:;:;::|

投げ出してたけどもう一回読んでみようかなぁ

≪PQシステムが決定手続きをもつことは、ある事実から断言できる。その事実とは、PQシステムは長さを伸ばす規則と縮める規則の対立する流れによって複雑にされていない、ということである。
　PQシステムには長さを伸ばす規則しかない。どんな形式システムでも、短い定理から永井定理を作ることはできるがこの逆はできないものには、その定理に対する決定手続きがある。≫(p.65)

　この御本人の解説に付け足すところは殆どないんですが、決定手続きにも二つの方向からのアプローチがある、という話までまとめましょう。

　１．トップ・ダウン（上から下）
　２．ボトム・アップ（下から上）

　「下」とは、公理に近いことです。システムの最下層に公理があります。公理はシステムの「礎」です。上に行くほど公理から遠ざかり、同一層にある定理の数が増えていきます。つまり、システムを逆ピラミッド型にイメージします。
　すると、トップ・ダウンの方法である文字列Pの定理性を検証するには、Pから公理に近づいていけばよい。Pから作り出される定理は、必ずPよりも小さくなる、という点がポイントです。
　逆に、ボトム・アップのやり方なら、公理から上に向って定理を次々に導出していく。見事Pにたどり着けばめでたしめでたし、辿り付けなくても、「Pよりも長い」定理の層まで来たら、そこで停止すればよい。

長い、、、、
みんなどのくらいで読み終わったのん？

活きろ！

図と地、DNAの情報がDNA本体にあるのか解釈するほうにあるのか
とかが面白かった。感想。

あーげ！

この本って結局何が言いたいわけ？

（ ﾟДﾟ）
（ﾟДﾟ ）
(;ﾟДﾟ)

>29
「数学ってのは面白いんだぜ」

>>29
おれって頭いいんだぜ。

俺もGEB読んだら天才または天使になったよ！げぶ！
天使のブラAGE！

>>33
＞天使のブラ
朝からﾜﾗﾀ

>>34　どうも、おはようございます。

>>35　おはようございます。調子はどうですか？

ほしゅ！ほしゅ！

ほしゅ！ほしゅ！

ミックさん忙し過ぎて諦めたのかな。。。
今度読む予定なので、上げとこ。

>>21
でもそこでこんぷたネタふらんと ELIZA とかチューリングテスト(の話あったよね)
の伏線張る場所かなり後になっちゃう。
亀とアキレスと蟹のとこ(でDNAなんだっけ)、たぶん柳瀬が訳やってるところが
すげえ好きっす。
>>31
数学だけじゃないだろ。「自己言及する体系」だと思はれ。だから哲学も当然入る。
この人のおやじさん、そいえばヘーゲル屋さんだよね。
家の家業、哲学……うーむ、あんまりそそんないかも。

ミックさんどこいったの？

>>41
間違いなく逃亡した。

あるいは不思議の環

これってなんかペンローズの「皇帝の新しい心（だっけ？」に似てるよね。

あげてみる