『C言語による計算の理論』
鹿島亮著
おもしろいし、読みやすい
テーマの一貫性があって、この本一冊で体系的な学びができる
伏線が多い。
前章の章末問題で出て聞か関数を証明の道具に使うこともある
逆に言えば、いくつかの章を飛ばして後から読む、というのはかなりやりにくいかも知れない
全体像
用語
自然数
0を含む
\vec{n}
自然数の列
(n_1,n_2,\cdots,n_k)のこと
これは長さがkの列
「\vec{n},\vec{m}が等しい」とは、要素と並びと長さが全て等しいことを指す
()
自然数の空列
\mathbb{N}^k
長さkの自然数列全体の集合
f(\vec{n})\downarrow
\vec{n}がfの定義域に入っていることを表す
全域関数になっている
f(\vec{n})\uparrow
\vec{n}がfの定義域に入っていないことを表す
部分関数になっている
お手上げ
f(\vec{n})=g(\vec{n'})
(A\land B \land C) \lor Dを満たす
A~Dは以下の通り
A:=f(\vec{n})\downarrow
B:=g(\vec{n})\downarrow
C:=f(\vec{n})とg(\vec{n'})の値が等しい
D:=f(\vec{n})\uparrow\land g(\vec{n})\uparrow
\lang a_1,a_2,\cdots,a_n\rang
(a_1,a_2,\cdots,a_n)のコード
自然数
原始条件式
2つの数式を比較演算子で結んだもの
ex.
a >= 30 , b != d 複合条件式
原始条件式と論理演算子の組み合わせでできる式
ex.
(((x%3 != 0) || (x%5 != 0)) 関数プログラム
p.9 のような形のプログラム
k入力プログラム
関数プログラムのうち、引数の数がk個のもの
k入力プログラムPが、自然数上のk変数部分関数fを計算する
任意の自然数n_1,n_2,\cdots,n_kに対して以下が成り立つこと
f(n_1,n_2,\cdots,n_k)\downarrowならば、Pの入力変数にn_1,n_2,\cdots,n_kをセットして実行すると、f(n_1,n_2,\cdots,n_k)の値を返り値として終了する
f(n_1,n_2,\cdots,n_k)\uparrowならば、Pの入力変数にn_1,n_2,\cdots,n_kをセットして実行すると、永久に止まらない
条件付きデクリメント文
hoge--' hoge が0以上の場合は1減算し、0の場合は0のまま1章
gが計算可能→fは計算可能、のとき
cf(x) {
if(g(x) % 2 == 0) return(0);
else return(1);
}その対偶、fは計算可能でない→gは計算可能でない
も成り立つが
fは計算可能→gは計算可能
は必ずしも成り立たない
扱うコードの文
代入文
インクリメント文
デクリメント文
if文
while文
return文
関数は再帰できない
2章
ジャンププログラム
変数名は
v1 , v2 ,..どんな関数プログラムもジャンププログラムに変換できる
3章
任意のプログラムを
code 化することで、ユニークな自然数に対応できる4章
この本のS-m-n定理は、後半の部分適用なので微妙に分かりづらい(そんなかわらんが)
それと、本書の説明は仮引数のことを言っているのか、実引数のことを言っているのか明示されておらず、文脈で理解しないといけないので、最初混乱した
その1って不動点の説明
ロジャースの不動点定理が近い
5章
6章
7章
8章
9章
10章
この図を更新したい
11章
ラムダ計算について。
だいたい知ってる内容だった