コンピュータサイエンス 4/27

「計算可能な関数とはどんなものか」を調べる試みとして原始帰納的関数がある。以下入力、出力ともに自然数であるとする。

1.定数関数をK[m,n](x1,x2,...,xn)=mで定義する。これは一定個数の任意の入力に対してある定数を返す関数である。例えば:
K[3,4](3,5,7)=4
この関数は入力の値を無視して常に4を返す。
2.射影関数をP[n,i](x1,x2,...,xn)=xiで定義する。これは一定個数の任意の入力に対してある個数番目の引数を返す関数である。例えば:
P[3,2](3,5,7)=5
3.後者(successor)関数をS(x)=x+1で定義する。これは引数の次の自然数を返す関数である。例えば:
S(5)=6

これらを次のルールで組み合わせて得られる任意の関数を原始帰納的関数とよぶ。

1.定数関数、射影関数、後者関数は原始帰納的である。これを初期関数とよぶ。
2.m個の入力をもつ関数fとn個の入力をもつ関数f1～fmが原始帰納的ならば、n個の変数をもつ合成関数
g(x1,x2,...,xn)=f(f1(x1,x2,...,xn),f2(x1,x2,...,xn),...,fn(x1,x2,...,xn))
は原始帰納的である。例えば:

f(x1,x2,x3)=x1+x2+x3
f1(x1,x2)=x1+x2
f2(x1,x2)=x1+2*x2
f3(x1,x2)=2*x1+x2

とするとき合成関数g(x1,x2)=f(x1+x2,x1+2*x2,2*x1+x2)=4*x1+4*x2
3.n個の入力をもつ関数fとn+2個の入力をもつ関数gが原始帰納的ならば
h(x1,...,xn,0)=f(x1,...,xn)
h(x1,...,xn,y+1)=g(x1,...,xn,y,h(x1,...,xn,0))
で定義されるhは原始帰納的である。

さて、以上で定義した原始帰納的関数がどのような意義をもつのか。直感的に、原始帰納的関数は計算可能（プログラミング可能）である。例えば足し算をする関数をadd(x,y)とすると、これは

add(x,0)=P[1,1](x)=x(つまり恒等関数、入力をそのまま返す関数)
add(x,y+1)=S(P[3,3](x,y,add(x,y)))（既に定義されているadd(x,y)の次の自然数を返している:x+(y+1)=(x+y)+1）

で定義してやればよい。他に引き算、掛け算、べき、階乗、最大値、最小値や平方根の整数部、円周率のn桁目など殆ど思いつく限りの実用的（整数値）関数は原始帰納的である。

では逆はどうか？計算可能な関数は常に原始帰納的、つまり上のルールに則る初期関数の組み合わせに還元できるのか。
答えはnoだ。（これがyesなら計算可能性の数学的定義は完了したことになるのだが・・・）
例えばAckermann関数というものが存在する:

ack(0,n)=n+1
ack(m+1,0)=ack(m,1)
ack(m+1,n+1)=ack(m,ack(m+1,n))

具体的には:

ack(0,1)=2
ack(0,1)=3
ack(1,0)=ack(0,1)=2
ack(1,1)=ack(0,ack(1,0))=ack(0,2)=3

Ackermann関数はどんな原始帰納的関数よりも早く増加する関数である。例えば:

ack(2,1)=ack(1,ack(2,0))=ack(1,ack(1,1))=5
ack(3,1)=ack(2,ack(3,0))=ack(2,ack(2,1))=13
ack(4,1)=ack(3,ack(4,0))=ack(3,ack(3,1))=65533

この関数は原始帰納的ではないが計算可能であり、プログラムも書ける。このように、原始帰納的関数は計算可能性を定義するには不十分なのである。（ちなみに、Ackermann関数が原始帰納的でないことを示す例題もあるが難しいらしい）

review!

　ブックレビューじゃないよ。ごめんね。

　某数学者のたまわく、最も効率よい勉強の秘訣は一に論文を書くこと、二に教えること。

　ってわけで(?)、ヤル気が花粉のように湧き出ているうちにまとめ、まとめ。まぁ多分僕以外全然面白くないと思うけど、ひょっとしたらどんな内容か知りたい人もいるかもしれないので。

---

計算機科学

　テキストはGlynn WinskelのThe Formal Semantics of programming Languages:An Introductionという本に添っているが今のところどうでもよい。

　プログラム言語の意味論には3通りある。操作的意味論operational semantics、表示的意味論denotational semantics、公理的意味論axiomatic semanticsである。後者になるほど抽象化するのだが、ここではまず操作的意味論を扱い、小さな命令型プログラミング言語IMP(Imperativeの略)を想定して話を進めるようだ。

　まず面白い、と思ったのはプログラムの実行過程における状態の定義。実行状態σとは、算術式の集合から整数の集合への関数である。算術式とは3とかa+3とかx*yとかそういう式だと思えばよい。状態σのもとで算術式aを評価（要するに計算）した値がnであるとき、これを<a,σ>→nと書く。これは表記上の問題で大したことではない。参考までにこれは状態の集合と算術式の集合と整数の集合の直積上の三項関係であるが、これもσが一変数関数なのだから当然だ。

　プログラムは状態σのもとで一つ一つコマンドを実行する。これは例えばソースコードの1行に相当する。操作的意味論における評価の表現は先の通りだが、コマンドの表現は<c,σ>→σ'である。これはコマンドcが状態σをσ'に変化させるという意味を表す。

　状態の定義から自然に状態の同値性が定義される。ある二つの状態σ1、σ2のもとで『同じ算術式a1,a2,...を評価した値がそれぞれ常に同じ』ならばこの二つの状態は同値とみなしてよい。同様に、二つの算術式a,a'が『任意の状態σと任意の整数nに対して<a,σ>→nと<a',σ>→nが同値』を満たすときa,a'は同値である（言い換えれば、どんな状態でも常に同じ値を返す2式は等しい）といい、二つのコマンドc,c'が『任意の2状態σ,σ'に対して<c,σ>→σ'と<c',σ>→σ'が同値』を満たすときc,c'は同値であるという。要するに、どんな状態に与える影響もそれぞれ常に等しい二つのコマンドは等しいとみなすということだ。

　コマンドの同値性を使うと一見ナンセンスな命題が導かれる。どの状態からスタートしても発散して答えが出ないプログラムは、互いに同値である。これは『<c,σ>→σ'⇔<c',σ>→σ'』という条件の(σ、σ')にはまる状態対が存在しない、つまり両辺が常にfalseということによるのである。ただプログラムの発散と停止の違いがまだ僕にはよくわかっていない。

　最後にやったのは、IMPにおいて

while b do c（これをwとする）

と

if b then c;w else skip

という二つのコマンドが同値であることを導出木の計算を使って証明する、ということだったが、ここらへんはチマチマしてるので省略。

　こんなところでいいのかな。kawayuさんあたり、補正があれば頼みたいです。なかなか要約の難しい内容だ。さてどこが面白いのか。状態と変数という数学的概念があって、ある状態のもとで変数を評価（計算）するとある数値がポンっと出る。何かに似てません？そう、量子力学ですよ。評価ってのを測定に変えるだけでそっくりそのまま。といっても僕がかじってたのはDiracの行列力学の方だけで、化学とかで扱う波動力学の方ではどうなってるのかさっぱりなんですが・・・素人目にもこんな類似があるとは思わなかった。まぁ、だからって量子コンピュータすごいとかそういう安易な展開にはならないわけですがｗ　ってかもう操作的意味論の話終わったっぽい。はえぇ。

コンピュータサイエンス入門

　目下のキーワードは問題、アルゴリズム、プログラムの3つである。コンピュータサイエンスにおける問題には入力だけでなく必ず出力（答え）がなければならない。一つの問題を解くのに必要なアルゴリズムが存在する場合は解ける問題、しない場合は解けない問題とよぶ。プログラムの停止性問題、最速のプログラムを見つける問題、Hilbertの第10問題（整数係数のDiophantos方程式が整数解をもつか判定する）は解けない問題に属する。講義は解ける問題と解けない問題の境界線を探る。

　解ける問題のうち常に現実的な時間で解けるものを実際に解ける問題という。例えば素因数分解は実際には解けない問題である。最大公約数を求める問題は実際に解ける問題だが、それを解くアルゴリズムは一つとは限らない。さらにEuclidの互除法という一つのアルゴリズムをとっても、それを記述するプログラム（ソースコード）は何通りもある。

　話変わって、整数から整数への関数の集合(N→Nと書くことにする)が可算（整数添字をつけて全ての要素を数えることができる）ではないことの証明。参考までに、有理数や有限集合は可算、実数は不可算である。背理法を使うが、そんなに難しくないので気構えないで頂きたい。仮にN→Nが可算とすると、f_0(x),f_1(x),f_2(x),...と全ての関数を列挙することができる。ここでg(x)=f_x(x)+1を考える。gは明らかに整数に対して整数を返す関数で、従ってN→Nの元だから整数kが存在してg(x)=f_k(x)と書けるはずだが、ここでx=kを代入するとおかしなことになる。つまりf_k(k)=g(k)=f_k(k)+1となるのだ。目からウロコである。このように矛盾を導く論法を対角線論法と呼ぶが、確かGoedelの不完全性定理の証明にも対角線論法が使われていたような気がしてびっくりである。

---

P.S.明らかに文章がおかしいところを修正しました。どうやら<と>をブログで編集しようとするとバグに悩まされるようです。

数論 11/13

Zagierの数論。Bernoulli数に関する計算で遊んだ。そんなに感動的な結果はなかったが・・・

・有名なBernoulli数とは次の展開係数である。（自然対数の底eと同じで定義の流儀には何通りかある）
t/(e^t-1) = ∑(B_k)t^k/k!(k=0～∞)
・暇人は次を確認せよ。
B₃ = B₅=B₇=…=0

・Bernoulli多項式
B_n(x) = ∑_nC_k・B_n-kx^k(k=0～n)
(1)B_n(0) = B_n
(2)(B_n(x))' = nB_n-1(x)
(3)∑B_n(x)tⁿ/n!(n=0～∞) = te^xt/(e^t-1)
(4)B_n(1-x) = (-1)ⁿBⁿ(x)
(5)B_n(x+1) = B_n(x)+nx^n-1(x)
(6)∑rⁿ(r=1～N) = (B_n+1(N+1)-B_n+1(0))/(n+1) = ∑(-1)^k・_nC_k・B_kN^n+1-k/(n+1-k)(k=0～n)

あーあ、めんどくさい割に見にくい。HTMLにTeXが組み込めればいいのに。。。

11/9 数論自主ゼミ

平方剰余について勉強。予習していなかったがいつもに比べると今回は進んだ。

MAT 10/30

院生のM氏の講義によるZagierの数論の勉強会が始まった（というか1ヶ月ぶりくらいに数学をやった）。この本は読んだことがないのだが、なるほど河田敬義よりも内容がコンパクトで勉強会には向いているかもしれない。今日はとりあえずDirichlet指標からL関数を導入した。少し面白かったので簡単にまとめると、(Z/NZ)^×上のDirichlet指標とは整数から複素平面への写像で、次を満たすものΧ（カイ）をいう。（Nを法とする）
(1)m≡nならばΧ(m)=Χ(n)
(2)Nとnが互いに素⇔Χ(n)≠0
(3)Χ(m)Χ(n)=Χ(mn)
　一般にn≡0,1に対してはそれぞれΧ=0,1となることが直ちにわかる。その他の値に対してもΧ=1となるものを主指標とよぶ。例えばN=2に対するDirichlet指標はΧ(0)=0,Χ(1)=1（主指標）しかない。N=3に対しては主指標Χ(0,1,2)=(0,1,1)の他Χ(0,1,2)=(0,1,-1)がある。N=4に対してはΧ(0,1,2,3)=(0,1,0,1),(0,1,0,-1),N=5に対してはΧ(0,1,2,3,4)=(0,1,1,1,1),(0,1,-1,-1,1),(0,1,i,-i,-1),(0,1,-i,i,-1)の４つとなる。N=7のときも同様に考えると6つのDirichlet指標がある。まだきちんと証明していないが、Nが素数のときはN-1個のDirichlet指標があってそれらは(f₀(i),f_N-1(i),…,f_N-1(i))(i=0,1,…N-1)と書けると考えてよさそうだ。例えばN=5のときはΧ=(0,1,e^nπi/2,e^3nπi/2,e^nπi)(n=0,1,2,3)というように同じ形に書ける。
　より一般的な形では、有限群G上の指標とは
　　GからC^×(0を除いた複素平面)への準同型写像Χ(a)Χ(b)=Χ(ab)
をいい、Dirichlet指標はG=(Z/NZ)^×（mod Nの既約剰余類群：0からNまでの整数でNと互いに素なものの集合と考えてよい）としたうえでZ/NZからCへの写像に拡張したものである。
　時間がないので続きはまた別の機会に。

数論自主ゼミ 10/7

2回生の先輩を新しく加えて初めからやり直すことに。なかなか進まないが、平方剰余にちょっと入る。

友人の疑問

どんな自然数nに対しても、pとp+2nがともに素数となるような組(p,p+2n)が存在するか？

9/25 Ahlfors

ζの導入部。理論の厳密な部分がよく分からない。でもまぁ漸く解析らしくなってきたしいいか。

9/20,22 数論自主ゼミ

なかなか進まない（10ページくらいしか進んでない）。やばい。（ちなみにずっと著者の河田敬義を景義だと思っていた）

9/16(SAT)-18(SUN) 合宿

吉田塾数学入門合宿の報告。

一応募集対象は全学に解放されていたようだが、生徒は1人を除いて全員理学部の総勢20人で2回が2人、3回が1人、他は1回生。チューターが4人、教授は加藤和也・向井茂教授の2人だった。

で、京北町の府立ゼミナールハウスというところに行った。他にもいろんな団体が来ていて、食堂では全員英語でしゃべっているどこかの大学のゼミの方たちなどと会った。もっとも向こうはできるだけ日本語を聞くわけにはいかないのでこちらとの接触を嫌がっていたそうですがｗ

18日昼に近くのマンガン記念館（昔鉱山があった）というところに歩いて行ったが、それ以外はずっと数学漬けだった。

加藤教授は数論で有名で、会ってみると分かるのだが変人の極めつけみたいな人だ。
敬虔な素数教徒で、「素数のうた」「素数踊り」というのをことあるごとに披露してくれるのですが、合宿中になんと新曲を3曲もリリースしてしまった。

一方の向井教授は不変式論の研究をしていらっしゃるそうで、授業はあまりよくわからなかった（正確にいうと何がやりたいのか分からなかった）が後でモジュライ（パラメータ空間）が超ひも理論に深く関係していることを知って、もっとちゃんと聞いとけばよかったと思った。

割とわかりやすかった加藤教授の授業は主に楕円曲線の話だった。本当は僕にわかるほど簡単な話ではないはずなのだが、要点をかいつまんで話をするのが上手な人でどのへんが面白いのか非常によく実感できた。

基本的なところですが楕円曲線の上に加法を定義できる、つまり群になっているという話が魅力的で目から鱗だった。
ちょうど理論物理への必要の延長で数論と楕円曲線に興味があって、保型形式、志村谷山予想(Fermatの最終定理の最後の砦だったらしい)、バーチ・シンナントンダイヤー予想についての簡単な導入にもなっていたしチューターさんも代数多様体、代数空間、代数スタック、ベクトル束の話とかしてくれたしもうとにかく刺激になりまくり。

16日の午後と17日の午前、18日の午前はずっと講義で、17日の午後にセミナー形式の演習の時間があって、夕食のバーベキューをはさんでひたすらみんなで8時間問題に取り組んで発表していた。
ああいうのがもっと頻繁にあればかなり鍛えられると思う。

生徒の方もかなり馬力のありそうな人が何人もいて、久々にモチベーションが上がった。
まぁ来るだろうなと予想していた人は全員きていたし。数学組の強豪が出揃ったとみても大げさではなさそう。

僕ももっと勉強しなきゃ。来年も行こうかなぁ。



で合宿で出た演習問題がいっぱいあるんですが、やたら数学的で意味不明な話題もどうかと思うので手頃（といっても解けなかったのばかりだけど）なやつを。

(1)整数成分の4×4次行列で行列式が1であるもののうち、自身は単位行列でないが5乗すると単位行列になるものの存在を示せ。
(2)球を任意に回転（自転）させてもとと異なる状態にするとき、回転の前後で移動しない球面上の点の個数は必ず2であることを示せ。

(1)はごり押しでなんとかできるのかもしれないけど、エレガントな解法が気になる。(2)は基本的には線型代数を利用するのだが、初等幾何でもなんとか解けるらしい。


そしてあの場にいた全員を悩ませた問題がこれ。

(3)arccos[cos(x)/(1+2cos(x))]を0からπ/2まで積分すると5π²/24になることを示せ。

道具に何を使うのかが全くわからず、出題ミスでは？との説まで流れる次第。


とにかく、数論って奥が深い。。。

Math 9/13

昨日の数論の自主ゼミは初回ということで（っていうかあまり予習できず）25ページくらいで終わった。
Euler関数、Moebius関数は高3のときに「代数学入門」を読んでいると出てきて何故代数なのに数論が出てくるんだろうと思っていたが、実はもっと進んだ代数の方でも数論の例が頻繁に使われる（イメージしやすいので）らしい。数論のゼミを始めようと思っているのも代数にとっかかりやすくするためなのだが、数論を読むためには代数の知識がある程度必要というジレンマで結局同時平行でやらないといけないようだ。
平方剰余の相互法則なんかも面白そう。


友人の問題
(1)0,1,2,3,…,9を適当に並べて、どの4つの数字を順番にとっても昇順にも降順にもならない順列が作れるか。例：3198450276なら9,8,4,0の順で選ぶと降順になり、1,4,5,7の順で選ぶと昇順になる。
(似た感じの問題なら見たことあるなぁ・・・)

(2)正方形を互いに大きさの異なる有限個の直角二等辺三角形に分割せよ。（・・・できるのか??）

問題 9/9

友人に紹介された問題。考えてみよう！
(1)n個の半球面が球面を覆っているならば、そのうちの4つで球面を覆えることを示せ。
(2)単位球面上のn点間の距離の二乗和の最大値をnの関数として求めよ。
(3)数字4を4つと四則演算＋－×÷及び括弧()、根号√、階乗!を使って41を作れ（記号の順番、回数は問わない）。

(2)は逆数和の最大値を計算するシミュレーションプログラムを以前書いたので少し書き換えれば数値演算だけはできそうですが・・・そんなに簡単な式で書けるのかな・・・？
(3)は実はネット上に答えが落ちています。気づかずに偶然見てしまったのですが、java scriptで見つけたというからまた驚き。41は4を4つ使って作れる整数の中ではかなり難しい部類に入ります。とにかく自力で答えを思いついたら・・・、すごいです。

8/25(THU) 代数

数論を勉強するため『抽象代数への入門』を読んでいるが、思ったより進まない。6章中第1章をやっと読み終えたところ。未だほんの基礎の基礎・・・orz
1章の要点は順序と代数系であるようだが代数系について混乱しそうなので適当にまとめ。

ある二項演算に関して閉じている集合をmagma、結合律を満たすmagmaを準群、単位元と逆元をもつ準群を群、可換な群をAbel群とよぶ。さらに「(i)加法に関してAbel群であり(ii)乗法に関して単位元をもつ準群であり(iii)加法と乗法に関して分配律を満たす」集合を環、任意の元が乗法逆元をもつ環を体とよぶ。
とまぁここまではなんでもないが、次にあまり聞いたことのない加群の話が出てきて戸惑う。可換性の問題から加群には左と右があるが、ここは要するにイデアルにつなげるために出てきた話という気がする。環R（実数体じゃないです）上の左イデアルとは「R-左加群としてのRの部分加群」と書いてあるが次の性質の方がわかりやすい。
I⊂RがR上の左イデアル⇔
「(i)Iは引き算に関して閉じている(ii)RI（Rの元とIの元をこの順番でかけたもの全体）⊂I」
同様に
I⊂RがR上の右イデアル⇔
「(i)Iは引き算に関して閉じている(ii)IR⊂I」
右イデアルでも左イデアルでもあるものをイデアルという。


がんばって読み進もう。

数論

わからん問題

次を示せ。
(1)Euclid整域は単項イデアル整域である
(2)単項イデアル整域は素元分解整域である

代数からきちんとやり直すべきか・・・

ていうかEuclid整域というものがそもそもよくつかめない。