て日々

2017年3月


2017年3月25日(土)くもり

土曜日だ。いつものように家でヘバる。昼前に近所の温泉に行き、昼食のうどんを作り、その片付けと並行して晩飯のための野菜炒めを作る。

ムスメが、自分の部屋の整理棚を改造するといって、大工仕事に勤しんでいる。電動ドリルを使うところだけ俺が代わりにやった他は、自分でいろいろ工夫していたようだ。


2017年3月24日(金)くもり

大学の卒業式。普段は着ないスーツを着て出かける。今年はうちの学科の卒業者がちょっと少なめな印象。謝恩会もわりと地味な印象である。こういうのはどうしても学年ごとのカラーが出る。

わがゼミの卒業生のうちkdくんは、ある製造業に就職。もうひとりのozくんはサークルでロックバンドをやっており、卒業後はライブハウスに就職する。そのozくんが、謝恩会にパンクなメイクで登場した。参加者一同ひっくり返ったが、事前に打ち合わせてあったので俺だけは驚かない。謝恩会では、花束とともに、記念品にジェットストリーム4色ボールペン+シャープという高機能そうな筆記具を頂戴した。ありがとう。


2017年3月23日(木)くもり

セガレの小学校の卒業式。あの息子が4月から中学生である。なんとまあなんとまあ。…って、俺も40年前に親たちに同じようなことを思わせたのかもしれないな。

建物内のワックスがけ作業をしているので、昼休み前後に階段が使えない。ひとつ下の階のトイレに行くためにいちいちエレベータを使わないといけない。午後、学生との面談が2件。Cooper本講読は発表者510くんの都合でお休み。

いま取り組んでいるhyperdegreeについての古い問題について、Chong and Yu «Recursion Theory» (De Gruyter, 2015) にちょっと間違ったことが書いてあることを発見。これは残念。自分が解こうと思っている未解決問題の正解が本に書いてあっても困るわけだが、だからといって間違ったことが書いてあるのが嬉しいわけでもない。今回はちょっと考えれば間違いだと俺でも判断できる話だったからいいが、もっと難しい箇所がこっそり間違っていたら、それこそ大変である。


2017年3月22日(水)はれ

先週の木曜日に準備不足で書けなかったMyhillの同型定理の話をしよう。

【集合の1-1帰着可能性について】自然数の集合 \(A,B\subseteq\mathbb{N}\) について、計算可能な1対1函数 \(f\colon\mathbb{N}\to\mathbb{N}\) で \[ x\in A\Leftrightarrow f(x)\in B \] となっているならば、\(A\) は \(B\) に1-1帰着可能であるといい、\(A\leq_1 B\) と書く。函数 \(f\) を明記したい場合は \(A\leq_1 B\) via \(f\) と書くことにする。関係 \(\leq_1\) は反射的(すべての \(A\) について \(A\leq_1 A\) via 恒等写像である)かつ推移的(\(A\leq_1 B\) via \(f\) かつ \(B\leq_1 C\) via \(g\) なら, \(A\leq_1 C\) via \(g\circ f\))である。そこで、\(A\leq_1B\) かつ \(B\leq_1 A\) のとき \(A\equiv_1B\) として関係 \(\equiv_1\) を定めれば、これは自然数の集合の間の同値関係ということになる。

【計算可能同型について】自然数の集合 \(A,B\subseteq\mathbb{N}\) について、計算可能な全単射 \(h\colon\mathbb{N}\to\mathbb{N}\) で \[ x\in A\Leftrightarrow h(x)\in B \] となっているならば、\(A\) は \(B\)と計算可能同型であるといい、\(A\equiv B\) と書く。この場合は添字1をつけない。計算可能全単射どうしの合成も計算可能全単射だし、逆写像も計算可能全単射になるから、関係 \(\equiv\) も自然数の集合の間の同値関係である。

と、ふたつの同値関係を定義したのだが、実はこのふたつは同じことなんだ、というのがMyhillの同型定理である。\(A\equiv B\) のとき \(A\equiv_1B\) となるのは明らかだけれども、その逆は自明ではない。

【Myhillの同型定理】\(A\equiv_1B\) ならば \(A\equiv B\) である.

この定理の証明を紹介するために、さらに少し定義をする。数の集合 \(A\) と \(B\) を固定する。数のペアの有限なリスト \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle \] が次の条件
 (1) \(i\neq j\) なら \(x_i\neq x_j\) かつ \(y_i\neq y_j\) である,
 (2) どの \(i\in\{1,\ldots,n\}\) についても \(x_i\in A\Leftrightarrow y_i\in B\) である
をみたしているとしよう。このとき、このリスト \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle \] をひとつの《部分同型》と呼ぶことにする。一様で計算可能な手段で部分同型を成長させて、\(\mathbb{N}\) 上の計算可能な全単射にまで育て上げようというのが、証明の戦略である。そのキモになるのが次の補題。

【補題】\(A\leq_1B\) via \(f\) とする. 部分同型 \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle \] と自然数 \(x'\in\mathbb{N}\setminus\{x_1,\ldots,x_n\}\) が与えられたとき, これに対して自然数 \(y'\in\mathbb{N}\setminus\{y_1,\ldots,y_n\}\) を見つけて \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle, \langle x',y'\rangle \] がふたたび部分同型になるようにする, 実効的な手続き(アルゴリズム)がある.

以下にその手続きを述べよう。図では \(n=3\) としているが手続は一般的に述べられる。

部分同型がある.
図0

定義域に新たな要素 \(x'\) を付け加えたとする.
図1

もしも \(f(x')\) が現在の部分同型の値域 \(\{y_1,\ldots,y_n\}\) に
属していなければ, \(y'=f(x')\) として手続終了.
図2

そうでなくて \(f(x')\) がどれかの \(y_i\) に一致しているなら,
図3

対応する \(x_i\) について \(f(x_i)\) を調べる.
もしも\(f(x_i)\) が部分同型の値域\(\{y_1,\ldots,y_n\}\) に
属していなければ, \(y'=f(x_i)\) として手続終了.
図4

その \(f(x_i)\) も部分同型の値域 \(\{y_1,\ldots,y_n\}\) に属していて
たとえば \(f(x_i)=y_j\) となっているなら,
対応する \(x_j\) について \(f(x_j)\) を見る.
以下同様, 部分同型の値域 \(\{y_1,\ldots,y_n\}\) に
属さない \(f(x_{何か})\) が見つかるまで繰り返す
図5

部分同型も函数 \(f\) も1対1だから、この手順は、部分同型の現在のサイズ \(n\) を越える回数繰り返されることはなく、いずれはどの \(y_i\) とも異なる \(f(x_{何か})\) が見つかり、\(y'\) が確定する。そこで、\(\langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle\) に加えてペア \(\langle x',y'\rangle\) をリストに登録する。手続きは以上である。

この手続きでは、数が集合 \(A\) や \(B\) に属するかどうかについて判断する必要はまったくなかったことに注意しよう。それでも、もしも \(x'\in A\) であれば \(A\leq_1 B\) via \(f\) という仮定から \(f(x')\in B\) である。ここで値の衝突があって \(f(x')=y_i\) だったなら、\(y_i\in B\) なので、部分同型の条件から \(x_i\in A\) であり、したがってまた \(f(x_i)\in B\) でもある。こうやって芋蔓式に、最終的な値 \(y'\) が \(B\) に属することが保証される。また\(x'\notin A\) であった場合には、これも同様に芋蔓式に \(y'\notin B\) であることが保証される。したがって、新しいリスト \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle,\langle x',y'\rangle \] もまた、部分同型である。こうして補題が証明された。

定理の証明にあたっては、この補題を \(A\leq_1 B\) via \(f\) という状況のほかに \(B\leq_1 A\) via \(g\) という逆向きの状況においても用いる。

【ステップ0】 部分同型の出発点として \[ \langle 0,f(0)\rangle \] をリストする。

【ステップ1】 もしも \(f(0)=0\) なら何もせず次のステップに行く、\(f(0)\neq 0\) ならば \(B\leq_1 A\) via \(g\) という状況に補題を適用して、 \[ \langle 0,f(0)\rangle, \langle x,0\rangle \] が部分同型であるような数 \(x\) を見つける。

以下、部分同型 \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle \] を少しづつ成長させていく。偶数番目と奇数番目のステップで役割をスイッチするところがポイント。

【ステップ \(2k\)】 数 \(k\) がこのステップまでに構成された部分同型 \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle \] の定義域 \(\{x_1,\ldots,x_n\}\) にすでに属していれば、何もせず次のステップに進む。数 \(k\) が部分同型の定義域に属していなければ、\(A\leq_1 B\) via \(f\) という状況に補題を適用して、 \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle, \langle k,y\rangle \] が部分同型であるような数 \(y\) を見つける。

【ステップ \(2k+1\)】 数 \(k\) がこのステップまでに構成された部分同型 \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle \] の値域 \(\{y_1,\ldots,y_n\}\) にすでに属していれば、何もせず次のステップに進む。数 \(k\) が部分同型の値域に属していなければ、\(B\leq_1 A\) via \(g\) という状況に補題を適用して、 \[ \langle x_1,y_1\rangle,\ldots,\langle x_n,y_n\rangle, \langle x,k\rangle \] が部分同型であるような数 \(x\) を見つける。

なので、ステップ \(2k\) が済んだ時点で、部分同型の定義域に数 \(k\) を含むことが保証されているし、ステップ \(2k+1\) が済んだ時点で、部分同型の値域に数 \(k\) が含まれることは保証される。この手順で部分同型にリストアップされる数のペアの全体を集めれば、\(\mathbb{N}\) 上の計算可能な全単射 \(h\colon\mathbb{N}\to\mathbb{N}\) が得られる。作り方から \[ x\in A\Leftrightarrow h(x)\in B \] となる。これでMyhillの同型定理が証明できた。

この定理の面白いところは、集合 \(A\) と \(B\) の素性にはまったく触れずに、計算可能な1対1函数 \(f\) と \(g\) の情報だけから計算可能な全単射 \(h\) が構成できるところだ。\(A\) や \(B\) には計算可能性や定義可能性の仮定は一切ついておらず、そのため応用範囲は広い。

たとえば、すべての計算可能部分函数の定義域の情報を体現する集合 \(K_0\) を \[ K_0 = \{\,2^e(2x+1)\in \mathbb{N}:\varphi_e(x)\downarrow\,\} \] と定義したとしよう。この集合は計算可能でない半計算可能集合である。この \(K_0\) と、停止問題に対応する集合 \[ K = \{\,e\in\mathbb{N}:\varphi_e(e)\downarrow\,\} \] とは、定義の見かけ上の違いにも関わらず、互いに計算可能同型 \(K_0\equiv K\) になるので、計算可能性理論の文脈では同じ役割を担うことが可能になる。それに、上の \(K_0\) の定義では数の対 \(\langle e,x\rangle\) を数 \(2^e(2x+1)\) で表現したが、これをたとえば \(2^e3^x\) で表現しても、またカントールの対函数 \(\frac{1}{2}(e+x)(e+x+1)+e\) で表現しても、互いに計算可能同型であって、重大な違いは生じないわけだ。

なお \(K_0\) に限らずすべての半計算可能集合が \(K\) に1-1帰着可能であることは16日木曜日の日記の最後にちょっと書いたとおり。逆に \(K\) を \(K_0\) に1-1帰着させるには、単に \(g(e)=2^e(2e+1)\) という函数 \(g\) を使えばよい。


2017年3月21日(火)くもり

春眠暁を覚えずというが、このごろ俺は毎朝寝坊気味である。なんとかせにゃならん。朝のうち小雨が降っていたので久々に傘を持って出かけたが、午後には雨も止み、夕方には薄日がさしていた。

このごろ、計算可能性理論の復習をしている。そういう目的には、自分でいろいろな証明を書いてみるのが一番なのだが、そのために、そろそろ具体的な計算モデルの定義を考えないといけない。アルゴリズムの記述としての可読性があることと、いわゆるクリーネのT-述語の定義がちゃんと書けることとの両立という点で悩んでいるところだ。アルゴリズムの記述として読めるためには、チューリング機械のプログラムのような判じ物ではなくて、現実のプログラミング言語のサブセットのようなものにするのがよいのだが、そのさい、言語仕様をあんまり欲ばると、記述力や可読性が向上するかわりに、理論的な解析が大変になる。クリーネのT-述語を記述するためにはプログラム言語の構文解析だけでなく意味論的な部分にも踏み込むことになり、なんだかコンピュータ科学に本格的に入門するハメになっちまいそうだ。まあそう言っても、たとえば先週木曜日の日記に書いた \(\varphi_e\) なんてものをちゃんと定義しようとするだけでも、クリーネのT-述語は必要不可欠なのだから、いつまでもこの部分をさぼっていてはいけない。いろんな本を読んで(高橋正子『コンピュータと数学』、Tom Stuart『アンダースタンディング・コンピュテーション』、篠田寿一『帰納的関数と述語』などなど)ひとつ考えてみよう。


2017年3月20日(月) 春分の日くもり

パソコンのMini Display PortからモニタのHDMI入力へ接続するケーブルをAmazonで購入。先日購入の液晶テレビをMacBook Proの外付けモニタとして使えないかと思ったのだが、接続してみたところ、思ったほどの性能が出ない。残念だが、まあ安価なテレビだから仕方ないとも思う。

半年ほど前に壊れて放置されていた妻の旧ノートパソコン(愛称: みやこはん)からデータを救済するためハードディスクを取り出した。ついでのことに、挿さっていた4GBのRAMボード2枚も取り出してMacBook Proに入れてみる。これまで4GBだったRAMが一挙に倍になったMacBook Proは、心なしか上機嫌に見える。


2017年3月19日(日)はれ

連休の中日だが、入試がらみの会議などがあるため、午後だけ出勤する。


2017年3月18日(土)はれ

計算可能性理論の古典的テキストであるHartley Rogers Jr.の “Theory of Recursive Functions and Effective Computability,” (MIT Press, paperback edition 1987)が届いた。あれも読まんならん、これも読まんならん。

しかしSacksの古い論文などを読んでいて疑問に思うのは、hyperdegreeの理論などに強制法を応用するさいに利用される分岐解析階層(ramified analytic hierarchy)と、それに対応する分岐言語は、どの程度本当に必要なんだろうか。あれは、もっと現代的な(相対的)構成可能的集合の階層の理論で置き換えることができないものなんだろうか。いや、それはこれから自分で考えるべきことなんですけど。

あと、計算可能性理論といえば、あの俊英「ゼルプスト湯呑み3号」が日本に帰ってくる。バークレーでのポスドク期間を終えて、次は名古屋に行くことになるとか。


2017年3月17日(金)はれ

午前中、どこかのカフェで勉強しようと思い、(三番町ガーデンプレイスカフェ改め)一番ガーデンに行ってみた。なんで三番町なのに一番なのかと思ったら、どうやらキリンの「一番搾り」のことらしい。昼間はカフェだが、夜はビヤホールとして営業しているというわけ。子供らが小学校低学年のころは、毎日のように通ったものだが、このごろはすっかりご無沙汰。かなり久しぶりだ。しかし店の雰囲気はあまり変っていない。

ホールの壁に添って並べられた『万有百科大事典』(小学館, 1976年)の第16巻《物理・数学》を開いてみる。「カントール」を村田全先生、「ゲーデル」を前原昭二先生、「非ユークリッド幾何」を志賀浩二先生が執筆している。なんとも贅沢な執筆陣だ。だが、感心して百科事典を眺めているうちに勉強を始めるのがすっかり遅くなり、ランチタイムに入って落ち着かなくなったので店を出る。給料日なので銀行へ行ってアレとコレのために資金を移動し、それから大学へ。天気もよく、昼休みの街を歩いて大学に向うのはいい気分だった。

katabami20170317
大学近くのカタバミの花

「一番ガーデン」にはまたちょくちょく足を運ぶことにしよう。


2017年3月16日(木)はれ

昨日に引き続き Moschovakis の «Hyperarithmetical Sets» を読む。もちろん俺とてこの道30年であるから、ここで展開されている「超算術的階層」の理論の大まかなストーリーは知っているが、同じ命題でも、G.E.Sacks の “Higher Recursion Theory” で読むのとは、表現や証明の方針がだいぶ違っていたりする。それに、たとえば、Boundedness Lemma のuniform版のことは知らなかった。勉強になる。

Cooper本講読ゼミは第9章に入った。ペアノ算術の決定不可能性(すなわち、与えられた命題がフォーマルな証明をもつかどうかを判定するアルゴリズムが存在しないこと)を証明し、続いて「ロビンソンのQ」の話に入った。これを済ませれば、述語論理の恒真論理式の集合が決定不可能であることの証明もできる。

やる気のないあひるやる気のないあひるやる気のないあひる

Moschovakisの論説に、「任意の \(\Pi^1_1\)集合は再帰的整列順序のインデックスの集合\(W\)に計算可能1対1函数で帰着可能」という補題が述べられていた勢いで、計算理論のいわゆる Padding Lemma について、昼食時にツイッターに連ポスした。その話をここに再現しよう。次の(BASICもどきの)プログラム

input x let y = x + 1 print y end

は、あきらかに以下のプログラムと同じ動作をする.

input x let z = x + 1 print z end

これは1を足す計算の結果を格納する変数を y から z に変えただけだから当然だ。なにも x と y と z でなくても、原理的には、構文規則に適ってさえいればどんな変数名でもいいので、

input mary let supercalifragilisticexpialidocious = mary + 1 print supercalifragilisticexpialidocious end

としても、同じ動作をする。もちろん、こんな無駄に長い変数名を使うのが実践的に正しいわけではないが、動作を変えることなく変数名を変えられることは、適切な変数名が使えるための必要条件でもある。

ともあれ、変数名を変えるなり、コメントを挿入するなりして、プログラムの動作に変更を与えずに、記号列としてのプログラムに変更を与える方法はいくらでもある。また、内部での動作が多少違っても、

input x let z = x + 5 let y = z - 4 print y end

というプログラムは、すべての入力に対して最初のプログラムと同じ結果を返す。このように、どんなプログラムに対しても、結果的に同じ動作をする別のプログラムを無数に作れる、というまったく当たり前の事実が、計算可能性理論では Padding Lemma と呼ばれている。

具体的な計算モデルで考える限り、まったく当たり前の話で、なにも Padding Lemma なんて大層に名前をつけるまでもないと思われそうだが、この補題には意外と使い道がある。再帰的函数の言葉で書けば、この補題は次のように述べられるだろう

Padding Lemma: 次の条件をみたす2変数の計算可能な函数 \(g(e,x)\) が存在する. すべての \(e\) と \(x\) と \(y\) について \[ \varphi_{g(e,x)}(y) \simeq \varphi_e(y) \] であり, かつ, 各 \(e\) ごとに対応 \(x\mapsto g(e,x)\) は1対1である.

ここで \(\varphi_e\) は数 \(e\) をプログラムの記号列に読み換えて実行した結果として実現される函数のこと。記号列としてのプログラムを適切な符号化で数値に変換すれば、計算の対象としての数にもなる。この「プログラムもデータである」という着想は、いわゆるフォンノイマン・アーキテクチャの根底にある着想であり、また計算可能性理論全体のキモである。また記号 \(\simeq\) はそうした函数が「定義されているかどうか」まで含めて、同じ結果を与える、という意味でのイコールである。

もちろん、単に再帰的函数の言葉で定式化したというなら、さきほどの自明な考察を難しい言葉で言い直しただけのことだ。だが、これをうまく使うことで、

任意の半計算可能な集合 \(A\subseteq\mathbb{N}\) は停止問題を表現する集合 \(K\) に、計算可能な1対1函数で帰着可能である. すなわち, 計算可能な1対1函数 \(f\colon\mathbb{N}\to\mathbb{N}\) が存在して \(A=f^{-1}(K)\) となる.

という定理が証明できる。あとで見るとおり、Padding Lemma を使わなくても、「計算可能函数で帰着可能」は言える。では「計算可能な1対1函数で帰着可能」にまで強めておくと何が嬉しいかといって、(シュレーダー=ベルンシュタインの定理の計算可能バージョンともいうべき) Myhillの同型定理という次の定理のおかげで、\(K\) のような性質をもつ集合が同型の意味で決まってしまうのだ。

Myhillの同型定理: ふたつの集合 \(A,B\subseteq\mathbb{N}\) が, 互いに計算可能な1対1函数で帰着可能であるならば, 計算可能な全単射 \(h\colon\mathbb{N}\to\mathbb{N}\) で \(B=h[A]\) となるものが存在する.

やる気のないあひるやる気のないあひるやる気のないあひる

というわけで、以下しばらく、計算可能性理論で重要な役割を果たす集合 \(K\) の話をする。その定義は \[ K = \{\,e\in\mathbb{N}:\varphi_e(e)\downarrow\,\} \] である。つまり、プログラム \(e\) に入力データとして \(e\) 自身を食わせたときに、計算が停止して結果が返ってくるような、そういう \(e\) の全体の集合で、チューリング機械の停止問題に対応している。たとえば \(e\) が「入力された文字列の文字数をカウントした結果を出力するプログラム」ならば、\(\varphi_e(e)\) は文字列としての \(e\) 自身の文字数を数えて出力して停止するはずだから、\(e\in K\) であるし、また \(e\) が端的な無限ループ

input x while (1) let x = x + 1 wend end

であれば、\(e\) 自身に限らず何を入力しても計算は停止しないのだから、\(e\notin K\) である。このように個別には \(K\) に入るか入らないかわかる場合もあるが「任意に与えられたコード \(e\) が \(K\) に属するかどうか判定するアルゴリズム」は存在しない。というのも、仮にそのようなアルゴリズムが存在したら、そのアルゴリズムを実装して、すべての入力 \(e\) に対して \[ \begin{gather} \varphi_h(e)=0\leftrightarrow \varphi_e(e)\downarrow\\ \varphi_h(e)=1\leftrightarrow \varphi_e(e)\uparrow \end{gather} \]

となるような、プログラム \(h\) が書ける。(ここで上矢印 \(\uparrow\) は、計算が停止せず結果が返ってこないこと、を表す。) さて、そうすると、\(\varphi_h(x)\) が1のときはすぐに停止し、\(\varphi_h(x)\) が0のときは無限ループに突入する、次のようなプログラム

input x while (\(\varphi_h(x)\)==0) wend end

だって、書けるはずである。いまこのプログラムを \(c\) とすると、 \[ \varphi_c(e)\downarrow\leftrightarrow \varphi_h(e)=1\leftrightarrow \varphi_e(e)\uparrow \] なのだから、とくにプログラム \(c\) に \(c\) 自身を入力して走らせれば、 \[ \varphi_c(c)\downarrow\leftrightarrow \varphi_h(c)=1\leftrightarrow \varphi_c(c)\uparrow \]となるが、これは矛盾である。だから、\(e\) が \(K\) に属するかどうかを判定するアルゴリズムは存在しない。\(e\in K\) であるならば、\(\varphi_e(e)\) の計算をすることによって、そのことは有限ステップで確証できるわけだ。しかし、\(e\notin K\) であるときに、そのことを確証するアルゴリズムがない。

この \(K\) のように、入力された数 \(x\) が集合 \(A\) に属しているときには計算が終了し、そうでないときには計算が終了しない、そういうアルゴリズムが存在する集合 \(A\) のことを「半計算可能集合」とか「再帰的可算集合」とか言う。\(K\) は計算可能でない半計算可能集合の典型例なのだ。

この定義から、半計算可能集合というのは、あるプログラム \(e\) によって、 \[ W_e:=\{\,x\in\mathbb{N}:\varphi_e(x)\downarrow\,\} \] の形に書ける集合のことだ、とわかる。

これら半計算可能集合のうちで、\(K\) が「最強の」集合であることが、次の補題からわかる。

補題: 次の条件をみたす計算可能な函数 \(f(e,x)\) が存在する. 任意の \(e\) と \(x\) について \[ \varphi_e(x)\simeq\varphi_{f(e,x)}(f(e,x)) \] となる.

その証明は、何を入力されてもそれを無視して、プログラム \(e\) に数値 \(x\) を入力したのと同じ計算をするプログラムを、\(f(e,x)\) とする、というだけ。\(e\) というプログラムの入力文まわりにちょっと手を加えるだけだから、なんでもない。どんな \(e\) とどんな \(x\) に対しても、 \[ x\in W_e\leftrightarrow f(e,x)\in K \] となるから、どの半計算可能集合のことも、しかるべき計算可能函数を介して \(K\) にお伺いを立てればわかってしまう。その意味で \(K\) は半計算可能集合のうちで「最強」である。もっとも、その意味で「最強」な半計算可能集合は \(K\) のほかにもいろいろある。それらの関係を調べるにあたって、1対1帰着可能性とMyhillの同型定理が効いてくるわけだ。そう思うと、Padding Lemma も侮れない。


2017年3月15日(水)はれ

このごろはhyperdegreeに関連する問題に取り組もうとしている。そのこともあって、Y.N.Moschovakisの論説 «Hyperarithmetical Sets» (著者のWebサイトでダウンロード可能) を読みにかかる。これは計算可能性理論の泰斗であるMartin Davisの業績をまとめた本 “Martin Davis on Computability, Computational Logic, and Mathematical Foundations,” (Springer, 2017)のなかの一章であるらしい。Moschovakisらしく明快で行き届いた論説だ。

帰り道、元町珈琲に寄ってMoschovakisの論説の続きを読んだ。


2017年3月14日(火)はれ

生協に行ったら洋書ディスカウントセールというのをやっていた。丸善で売れ残った洋書のバーゲンらしい。Doverあたりのペーパーバックが定価の3割ほどになっている。その中に、Pillayの “An Introduction to Stability Theory” があった。税別500円なので買うことにした。本当は、このたび邦訳が講談社学術文庫に収録されたマクタガートの『時間の非実在性』を買いに行ったのだけど。

books20170314


2017年3月13日(月)くもり

黒いウールのコートはそろそろおしまいにしたいが、このごろは、昼のうち暖いと思っても夜に寒くなるので、なかなか油断できない。吉田夏彦『論理と哲学の世界』(ちくま学芸文庫)を読み終えた。《読書管理ビブリア》の記録に残っている限りでは、今年まだ4冊目である。まったく少ない。さらにいろいろ読まなくちゃ。

ピアノのレッスンは先生の都合によりお休み。

夜、卒業を間近に控えたゼミ生のKDくんと038くんに、就職と卒業の祝いとして、花園町の「や台ずし」でメシをおごる。地味に楽しかった。この店は気軽に“回らない寿司”が食えて酒が飲めるので、こういう時には重宝する。

3人でしゃべりつつ飲み食いしていると、意外なことに、ゼミ生たちは「ゼミのときでもいつでも、先生は、なんか楽しそうにしている」と言う。酒飲んで無駄話してるときはいざ知らず、どうしてゼミの指導中に楽しそうにしていると見えるのか、自分では理解できないが、それはそれで、そういう風に見てもらえるのはありがたいことだ。「いつもつまらなそう」とか「いつも怒ってるように見える」とか言われるよりはよほどいい。


2017年3月12日(日)はれ

午前中は後期日程の入試の監督。午後、となりの松山大学でやっているムスメの学校の芸術文化発表会というのに行き、お茶席で抹茶をいただいた。昼飯は、清水公民館の並びの手打うどん店「鶴鶴」に行った。この店、四半世紀にわたって前を通りすぎるばかりで、きょう初めて入った。つゆの味は普通だったが、コシのあるよい麺であった。

帰宅して昼寝して怖い夢を見た。目をさますと家に誰もいなかったので、よけい怖くなった。とはいえ事件でもなんでもなくて、親子でスーパーに買いものに行っていただけだそうだ。


2017年3月11日(土)はれ

このごろ土曜日は毎週くたびれて寝てばかりいる気がする。きょうも家からほとんど出ず。ただし、ピアノのお稽古は普段より多めにやった。演奏会の出し物にするかどうかはともかく、ムード音楽の定番曲を1曲練習しておくことにした。

さてさて、池上くんに今週いろいろ教えてもらったことは、Ralf Schindlerの2004年ごろの論文(Forcing axioms and projective sets of reals, Proceedings of FotFS III, in: “Classical and new paradigms of computation and their complexity hierarchies” (Löwe et al., eds., Kluwer 2004), pp.207-222. PDF)を読めばひととおり書いてあるらしい。まあ、済んだ話だろうとは思っていたし、それは別にかまわない。


2017年3月10日(金)くもり

昨日の話の続き。可算鎖条件をみたす強制概念で \(\exists a\in\mathbb{R}(\mathbb{R}\subset L[a])\) を強制できるための十分条件が《連続体仮説が成立していて、本物の \(\aleph_1\) がある \(r\in\mathbb{R}\) に関する \(L[r]\) において弱コンパクト基数になっていない》という形に弱められることがわかる。ひとまずこれまでにわかったことをTeXでまとめる。


2017年3月9日(木)はれ

休日出勤の代休日。午前中は家にいて、パソコンでマルコフ連鎖のプログラムを書いて試す。午後、電車で街へ出かけて、アエル松山のブランチコーヒー(branch coffee)に行った。なかなか居心地がよく、コーヒーのフレッシュな香りがうれしい。記述集合論と巨大基数と強制法の関連について、昨晩ツイートしたら、今朝になって池上くんがいろいろ教えてくれたので、ノートをとりながら確認する。疑問点についてツイッターで池上くんに照会したら、リアルタイムに返事が来た。ちょっとした公開セミナーだ。

さて、Cooper本ゼミをキャンセルするのを忘れていたので、午後4時半に大学に顔を出したのだが、しばらく誰も来なかった。こりゃゼミは流れるなあと思った頃に510くんが登場。聴講者の院生2人が来ないのでゼミは流れるしかない。510くんの問いに答えて、理論の完全性と決定可能性について少し議論した。

帰りは元町珈琲でさっきの強制法の話の続きを考える。池上くんが証明したのは《もしも \(0^\sharp\) が存在しなければ, あるジェネリック拡大で \(\exists a\in\mathbb{R}(\mathbb{R}\subset L[a])\) が成立する》だった。これは特定の(かなり大きい)基数を可算に潰す強制法を使う。俺が考えていたのは少し違って、もしも連続体仮説CHが成立していて、しかも \(\exists r\in\mathbb{R}(\aleph_1^{L[r]}=\aleph_1^V)\) であれば、almost disjoint forcingの方法で \(\exists a\in\mathbb{R}(\mathbb{R}\subset L[a])\) を強制できるだろうということだった。連続体仮説を仮定しなければならないのが邪魔っけだが、これは外せない。というのも、 \(\exists a\in\mathbb{R}(\mathbb{R}\subset L[a])\) という命題は連続体仮説を含意するいっぽうで、almost disjoint forcingは可算鎖条件をみたし基数を壊さないので、連続体仮説を強制できないのだ。

家や研究室にいるときはこういう数学になかなか集中できないので困る。


2017年3月8日(水)くもり

昨日もそうだったが、朝のうち暖いのに午後からどんどん寒くなった。曇っていると思っていたら晴れ、晴れたかと思ったら曇り、にわかに雪が舞ったかと思ったらまた晴れる。わけがわからん天気だ。だが、大荒れになるよりはいい。昨日の反省の上に立って、きょうは一日有意義に過ごすはずだったのだが、それはどうやら単なる希望に過ぎなかった。一昨日届いた『数学ガイダンス2017』の第3部「身につけておきたい理系マニュアル」を読んで、なるほどなあ、と感心しているうちに一日が終わってしまいそうだ。これではいけない。

これではいけないので、せめてもう一冊読むことにしよう。谷岡一郎『データはウソをつく‐科学的な社会調査の方法』(ちくまプリマー新書, 2007年)を読んだ。内容は、まずは、報道やネットで得られる情報をまず疑ってかかりなさい、本当にそうかと自分で考える習慣をつけなさい、という話。結城浩の近著『数学ガールの秘密ノート/やさしい統計』(SBクリエイティブ, 2016年)でも槍玉に上げられていた、間違った印象へ誘導するグラフの見せかたなどの話。さらに、これが本題だと思うが、信頼するに足るデータを自分で集めるには、こんなふうに調査する必要がある、という社会調査の方法論の話。コラムといしいひさいちの漫画がいい具合に挿入されている。話の性質上、時事問題への言及が多く、著者の語り口に耳が(目が?)なじんでくるとその部分がとりわけ面白く感じた。しかしまあ、初版刊行の2007年から今までの間に我々を襲った出来事(地震とか原発とか都知事なんちゃらとかSTAPなんちゃらとかトランプなんちゃらとか…)を考えると、同じ著者にいま同じ趣旨の本を書いてもらって読んだほうが、断然面白いはずだとは思う。まあ、ないものねだりだ。

やる気のないあひるやる気のないあひるやる気のないあひる

俺は基本的に無能でぐ〜たらなくせに、この「て日々」を毎日更新せねばならないという縛りを自らに課しているもので、昨日の日記なんかでもそうだが、わざわざバカをさらけ出すようなことしか書けない日がある。そうなると「て日々」の更新が苦痛になる。かといって、気が向いたときだけ書く、というスタイルでは絶対に続かないこともすでに実証されている。考えてみれば、ヒトサマに読んでいただくに値する日記が毎日欠かさず書ける人生なんてのもありえないわけだが、それでも、日記をやめてしまうのが正しいわけでもなさそうだ。実際、中断しても結局再開しているわけで、書くこと自体は嫌いでないのだし、誰よりも俺自身が「て日々」のいちばんの愛読者なんだし。

それなら、情けないことを書かずに済むように心がけて生活すべきだ。せめて、もっと本を読まなくちゃいけない。


2017年3月7日(火)はれ

昨日ジュンク堂で買った本(S.S.Chang著『RとRubyによるデータ解析入門』(オライリー, 2013年))で、Shoes というRubyベースのGUIアプリケーション構築ツールのことを知った。チュートリアルを見ながら、夢中になって試していたが、午後に会議があることをすっかり忘れていた。ごめんなさい。

秋山智俊『恋するプログラム Rubyで作る人工無脳』(マイナビ)という本に登場する「人工無脳」は VisualuRuby というツールキットでGUIを構築していたのだが、これは少々古く、またWindows専用である。まあ『恋するプログラム』自体がちょっと古い本(2005年4月初版)の復刻だから、これは仕方がない。なんとか本の内容を自分のMacで再現する方法がないかと思って、見よう見まねでRuby/Tkのインストールを試みて失敗したりしていたところへ、別の本でShoesのことを知ったので、どんなものか試してみたという話。

『恋するプログラム』のサンプルとして配布された画像データはBMP形式。Shoesの扱うのはPNGかJPEGだ。BMPファイルを「プレビュー」で開けばPNGに変換するのは簡単だが、なにせファイル数が多い。同じデータの使い回しが多いとはいえ、アーカイブ全体で340個のBMPファイルがある。一つ一つ手作業ではやってられないのだが、かといって、高価なソフトウェアツールを買って使い方を勉強して、とかいうのもイヤなので、かれこれ十年ぶりにAppleScriptを書いて作業を自動化した。そもそもAppleScriptの書き方なんかすっかり忘れていたし、スクリプト言語のくせに文字列の操作が不得手な不思議な仕様のため、ファイル名の.bmpという拡張子を.pngに置換するだけでもひと工夫必要で、思いのほか時間がかかったが、あちこちのフォルダに散在しているBMPファイルを、いちいちフォルダを開かずに一斉に処理できたので満足だ…

いやいやいや、満足していてはいけない。

だいたい、なぜこの『恋するプログラム』を読んでいるかというと、人工無脳をとっかかりとしてプログラミングを勉強して、自分なりに《自然言語処理》ってのをやってみたいからだ。最初に言ったChangの本だってそのために買ったのだ。それならGUIの再現なんかより、形態素解析ライブラリの使い方や自動学習の実装の部分を先に勉強すべきじゃないか。たかが画像の変換の自動化のスクリプトひとつ書くのに何時間もかけるなんて。会議をすっぽかしてまで何をやってんだろ。それに、プログラミングの勉強自体、本業とまったく無関係とまではいわないが、いわば道楽である。

夜になって我に返って、しょんぼりしてしまった。


2017年3月6日(月)くもり

入試スケジュールその他の年度末業務のあいなかの週。キャンパスが妙に静か。夜、ピアノのレッスンからジュンク堂書店といういつものコース。

日本評論社から数学セミナー増刊『数学ガイダンス2017』が届いた。理系の大学生とくに数学専攻向けのガイドブックで、同様のものが毎年出ているようなのだが、今年のものには2013年4月号に掲載された特集記事「新入生のためのブックガイド」が収録されている。つまり、拙文が再掲されている。

数学ガイダンス2017表紙

いやまあ、拙文のことはこのさいよろしい。巻頭の真鍋大度さんへのインタビューを別にすれば、大部分は過去の「数学セミナー」からの転載だから、すでに「数学セミナー」を購読している人には改めて読めとは言わない。とはいえ、新入生を念頭に再編集されたというのはそれなりに有意義で、なにしろ、大学で勉強するいろいろな数学の分野をこれ一冊で一望できる。そのうえ、ノートの活用法、ギリシャ文字の書き方、といったガイダンスならではの記事や、LaTeX入門、数学ソフトウェアGeoGebraの紹介なんてのもある。数学科の新入生や、とりわけ、大学では数学を専攻しようかなと思っている高校生なんかにはお薦めだ。


2017年3月5日(日)くもり

セガレは小学校区の公民館イベント「城山サーキット」に出かけた。セガレがもうすぐ小学校を卒業してしまい、毎年この時期恒例のこのイベントも今年で最後になる。これまでは母親がついて行っていたが、今回は友達と2人チーム。そういう意味では、セガレもずいぶん成長したものだ。

セガレがいないので、昼飯は3人で、近所の中華料理屋に出かけた。ボリューム満点で妻とムスメは完食できず、パッケージをもらって持って帰ることに。

レンゲの花。かなりのアップ
写真は近所の田んぼのレンゲの花

今春は「関西すうがく徒のつどい」が開催されないのだが、それはもちろん、誰も何もしていないという意味ではない。昨日から今日にかけて、神戸大学で学生団体POMB主催の2017年春合同セミナーという数学系のインカレセミナーが開催されたらしい。「つどい」常連のメンバーも何人か参加したようだ。これでいいのだ。なにも「つどい」につどいを独占させておく必要はまったくない。皆がそれぞれ自分のやりたい企画をやり、乗りたい人が乗る。SNSをフル活用してその情報を互いに交換しあう中から、さらに新しい企画が生まれる。そういうリゾーム的というかハイパーテキスト的な展開が、若い人たちにはふさわしい。


2017年3月4日(土)はれ

土曜日のお約束で、くたばって過ごす。昼飯にうどんを作る。実家からいちばん上の伯父さんの訃報。弔電を打つ。


2017年3月3日(金)はれ

午前中、新年度の卒業研究ゼミ生の配属が決まり、研究室にやってくる。96くんは論理学そのものに興味があるらしいので、戸田山和久『論理学をつくる』(名古屋大学出版会, 2000年)を最初から丁寧に読んでもらうことにした。109くんは集合論。ひとまず上江洲忠弘『集合論入門』(遊星社, 増訂版2013年)を読んでもらうが、着地点はもうちょっと先にしたいところ。

午後に学部の会議。そのあと、旧年度のゼミ生038くんが「卒業研究のまとめ」の原稿をもってきた。発表会で話すはずだった内容を紙に起こしたレポートである。面白い発表になったはずなので、インフルで来れなかったのは残念である。


2017年3月2日(木)くもり

先週池上くんに講演してもらったばかりだが、きょうも16時半からTGSAセミナーがある。講演者は島根の松橋さん。15時から同じ部屋で教室会議が開かれる。すんなりとは終わりそうにない波乱必至の議題が上っていて、最初から不吉な予感がしていたが、セミナーの時間が近づいても話が終わる気配がまったくない。先週に引き続き都城から来てくれたトモヤスさんとか弓削から来てくれた岩本さんとか野倉名誉教授とか、学外のセミナー出席者がドアを開いて部屋を覗きこんでは、困った顔をしている。結局、16時半ちょうどに、議長が会議を無理矢理終了させた。そのあと大急ぎ(約30秒)でTGSAセミナーの会場準備。

ただし、俺はTGSAセミナーを聴かず、先週できなかったCooper本講読を優先させてもらう。内容は第8章の後半。ゲーデルの不完全性定理を計算論の観点から証明するもの。証明はわかりよくなるが、しかし結果は少し粗くなり、ロッサーの改良や第二不完全性定理へ向かう筋道が見えなくなる。そこで、その部分を俺があとで補足した。増長天さまがそのアイデアに感心していた。

Cooper本講読ゼミが済んだら、急いで南堀端へ移動してTGSAセミナーの出席者に合流し、アミティエで会食。


2017年3月1日(水)はれ

思うところあって、ある古い論文をTeX化する作業。

イタリック補正の使用例

英語の数学論文では、定理などのステートメントは慣例上イタリック体 (例:Italic font style looks like this.) で組まれる。地の文の文字が右へ傾斜するわけだが、数学記号のなかには傾斜しないものもたくさんある。それで、f のような背の高い文字が傾斜しているあとに傾斜しない数学記号が来ると、文字と記号が近付きすぎるきらいがある。そこで TeX では各フォントの各文字にそれぞれ「イタリック補正」という量が定められている。これを入れて調整することで、文が多少なりとも読みやすくなる。

数式用イタリックフォントと文章用イタリックフォントの比較

数式に出てくる変数名などの文字には原則として数式用イタリックフォント (Math Italic) が用いられる。数式用イタリックフォントと地の文のイタリックフォントは少しだけ字体が違うのだけど、この画像でもわかるように、けっこうまぎらわしい。もっとも、これはTeXだけの問題ではなくて、英文の電子メールで数学の話をしている時なども悩みのタネになる。

あともうひとつ。TeXでいろいろなフォントを利用するのが簡単になってきたのは喜ばしいことではあるが、だからといって数式などで珍妙な記号を濫発するのは慎しみたい。書き手が組版テクノロジーを駆使して書いた文書であっても、読む側は百年来変わらぬ紙とペンで内容を追いかけなければならないからだ。記号が足りないというのも本当なのだろうけど、数式にドイツ風のひげ文字が出てくるたびに泣いている俺としては、凝った記号はなるべく使ってほしくない。せいぜい♢とか♣︎くらいまでにしておいてほしい。そういえば、『キューネン数学基礎論講義』では、数式番号が✌︎になっている箇所があったし、同じくKunenの論文には「証明終」の印が☕︎になっているのがあった。まあ、数学的なコンセプトを表わす記号でなく他の記号で代用してさしつかえないから、これはまだ許せる。『キューネン数学基礎論講義』でモデルの記号を古めかしいひげ文字で書いていたのには閉口したけど。