『C言語による計算の理論』
https://gyazo.com/1a48df6910750ed8f4730e0a3f0a4a55
おもしろいし、読みやすい
テーマの一貫性があって、この本一冊で体系的な学びができる
伏線が多い。
前章の章末問題で出て聞か関数を証明の道具に使うこともある
逆に言えば、いくつかの章を飛ばして後から読む、というのはかなりやりにくいかも知れない
全体像
https://gyazo.com/eca4fe2552b4712f17dbaf902b3ec7fa
用語
自然数
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)のコード
自然数
https://gyazo.com/81f4161bd35abde7d388fa26980bde0c
原始条件式
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は計算可能、のとき
code:c
f(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定理は、後半の部分適用なので微妙に分かりづらい(そんなかわらんが) それと、本書の説明は仮引数のことを言っているのか、実引数のことを言っているのか明示されておらず、文脈で理解しないといけないので、最初混乱したmrsekut.icon
その1って不動点の説明
5章
6章
7章
8章
9章
10章
この図を更新したい
https://gyazo.com/eca4fe2552b4712f17dbaf902b3ec7fa
11章
だいたい知ってる内容だったmrsekut.icon