岩波講座 ソフトウェア科学 12巻

幾つかの計算モデルについて書かれた本

各章が各モデルについてになっている

めっちゃ良書

ただ、各計算モデルについて詳しく知りたければ個々の本を読んだほうがいい

ページ数的に

計算モデルの概要を掴み、語彙を増やすにはめっちゃ良い本

4章のラムダ計算はめちゃめちゃ詳しい

この本を難しく感じる場合は、先に『計算モデルとプログラミング』を読むと良い

1章: 計算モデルへの招待

各計算モデルの概要

読んだ2019/12/16

2章: 機械モデル

計算機の基礎の誕生

計算機械を構築しようという試みと

計算の可能性と限界を知ろうとする試みが

互いに影響を及ぼしあって構築されてきた

チューリングマシンもラムダ計算も1936年なのか

その後の第二次世界大戦によって、計算機の構築も本格的になった

プログラムを計算機の記憶内に内蔵できるようになったのが計算機の発展に寄与した

チューリングマシンは停止性問題を考えるときには有効な手段だが、

実用的には扱いづらいし、実際の計算機ともかけ離れたもの

無限のテープとか言ってるしな

なので、もっと実際の計算機に近づけたものがRASPなど

章末にキーワードだけ書かれている抽象機械とはなんだ #??

読んだ2019/12/17

3章: 関数モデル

帰納的関数論についての章

この本の合成\circの書き方が一般のものと順序が逆だな

p.39

f(x_1,\cdots,x_n)は、定義された引数に対しては結果が求まり停止する

定義されていない引数に対しては停止しない

\mathcal{L}との関連性がわからんが？

引数が\mathcal{L}の中身なんか？

数値関数

\mathbb{N}^n\rightarrow\mathbb{N}な関数

n\in\mathbb{N}

この本特有の言葉なのかどうかは知らん

表記の意味

個数を特定しない変数の並び

\vec{x}:=x_1,\cdots,x_k

一応読んだ2020/1/2

最後の方の累積帰納あたりの読み方が雑かった

4章: 関数モデル

本書で使われる記号の意味

=は簡約の過程で得られる全ての項が同じ概念を表していることを示す

\twoheadrightarrowは、複数回の簡約を表す

\xrightarrow{\ast}_\betaとかのほうがわかりやすい気もするな

記号

\Lambdaはラムダ抽象の集合

p.77

要するに、木の中からある一つの節を定めたときに、それ自身とその全ての子のことを木領域と呼んでる

たぶん

以下を満たす\mathbb{N}_+^\astの部分集合

\{v\in\mathbb{N}_+^\ast|\exist w\in\mathbb{N}_+^\ast,u=v\cdot w,u\in D\}\subseteq D

\forall u\in Dに対して、

\forall i\in\mathbb{N}_+[u\cdot i\in D\Rightarrow\forall j\in\{1,\cdots,i\},u\cdot j\in D]

5章: 論理モデル

論理式自体は意味を持たず、解釈を与えた時に初めて意味を持つ

一階述語論理とか

証明についてとか

未読

6章: 書換えモデル

未読

7章: 代数モデル

未読