計算モデル
モデルを構成することをモデル化という
これは科学の多くの分野の基本的な手法
物理学で物体の運動を考える時に、剛体と重力場だけを考える感じ
ある視点において本質じゃないところは削ぎ落として定理を作っていく感じのことかなー、mrsekut.icon
プログラミングにおいても、そもそも現実世界を計算機内で扱おうなんて雑に考えれば無理そうだけど、単純なものから積み重ねていけばコードで世界を記述できるようになる
計算機科学内で扱われるモデルには、
計算機科学が誕生するよりも前からあった数学の概念が多く影響している
関数、論理、代数など
プログラムを代数と捉えることで、値の集合の構造を見つけることができる
値というのは、プログラミングにおける値やデータと見ていいと思うmrsekut.icon
プログラムってデータの小さな変形の組み合わせだが、データに対して「意味」がわかっていなければ、ただのデータの集合みたいになっちゃう
そうじゃなくて、この集合にちゃんと構造を入れて意味を与えようという感じ
様々な計算モデル
他
table:計算モデルの比較
モデルの種類 モデル中のの詳細 対象 変形 関係
機械モデル 記号 状態遷移 次状態関数が定める関係 ref 『(理論)12 計算モデルの基礎理論』.icon p.10
モデル間の複雑さ ref 『計算理論の基礎 3』.icon p.305
$ t(n)は$ t(n)\ge nであるような関数
$ t(n)時間NTMは、
NTMのいくつかの枝分かれの中で一番時間のかかるもののステップ数が$ t(n)であるようなNTMのこと
つまり、一番遅い枝を選んだら$ t(n)回のステップ数で停止する
参考