モデルを構成することをモデル化という

これは科学の多くの分野の基本的な手法

物理学で物体の運動を考える時に、剛体と重力場だけを考える感じ

ある視点において本質じゃないところは削ぎ落として定理を作っていく感じのことかなー、

プログラミングにおいても、そもそも現実世界を計算機内で扱おうなんて雑に考えれば無理そうだけど、単純なものから積み重ねていけばコードで世界を記述できるようになる

計算機科学内で扱われるモデルには、

計算機科学が誕生するよりも前からあった数学の概念が多く影響している

関数、論理、代数など

プログラムを代数と捉えることで、値の集合の構造を見つけることができる

値というのは、プログラミングにおける値やデータと見ていいと思う

プログラムってデータの小さな変形の組み合わせだが、データに対して「意味」がわかっていなければ、ただのデータの集合みたいになっちゃう

そうじゃなくて、この集合にちゃんと構造を入れて意味を与えようという感じ

様々な計算モデル

他

Brainfuckなど

ref p.10

モデル間の複雑さ ref p.305

全てのt(n)時間非決定性チューリングマシン(NTM)に対して、

それと等価な2^{O(t(n))}時間決定性チューリングマシン(DTM)が存在する

t(n)はt(n)\ge nであるような関数

t(n)時間NTMは、

NTMのいくつかの枝分かれの中で一番時間のかかるもののステップ数がt(n)であるようなNTMのこと

つまり、一番遅い枝を選んだらt(n)回のステップ数で停止する

参考