計算モデル
types:
抽象機械型…
en: abstract-machine …
命令型…
en: imperative …
関数型…
en: functional …
論理型…
en: logical …
programming languages:
並行並列性
並列モデルを別枠に立てることも
モデル
チューリング機械
流れ図
en: flowchart
by Neumann
有向枝
en: branch, arc
e.g. Scratch
具体例
順序機械
en: sequential machine
6つ組で定式化
subclasses
有限オートマトン
en: FSA
turing machine
register machine
subclasses:
counter machine
register machine
accumulator machine?
RAM
cf. Harvard architecture
RASPM
cf. Neumann architecture
書籍
『計算モデルとプログラミング』森北出版
halt' の定義の M の停止性が逆になってる？（図2.27, 28; p. 38）
主語の省略が読みづらいだけで、合ってた。
いや、やっぱり M も H も対応してないとヘンでは？？
対角化について、再び整理
Mが（Mに対して）…
停止する: 0|1
⇔$ \mathrm{halt}(\widehat{M},\widehat{M})=1
⇒$ \mathrm{halt'}(\widehat{M})=\bot
停止しない: ⊥
⇔$ \mathrm{halt}(\widehat{M},\widehat{M})=0
⇒$ \mathrm{halt'}(\widehat{M})=1
H′が（H′に対して）…
停止する: 0|1
⇔$ \mathrm{halt}(\widehat{H'},\widehat{H'})=1
⇒$ \mathrm{halt'}(\widehat{H'})=⊥
停止しない: ⊥
⇔$ \mathrm{halt}(\widehat{H'},\widehat{H'})=0
⇒$ \mathrm{halt'}(\widehat{H'})=1
errata
p. 38
すなわち，「$ H'が，入力$ \widehat{H'}に対して停止する」としたとき，関数$ \mathrm{halt}の定義から，$ \mathrm{halt}(\widehat{H'},\widehat{H'})=1となり，関数$ \mathrm{halt'}の定義より，$ \mathrm{halt'}(\widehat{H'})は未定義となる．しかし，$ \widehat{H'}は$ \mathrm{halt'}を計算するので，これは，「$ H'が，入力$ \widehat{H'}に対して停止しない」ことになる．
一方，「$ H'が，入力$ \widehat{H'}に対して停止しない」としたとき，関数$ \mathrm{halt}の定義から，$ \mathrm{halt}(\widehat{H'},\widehat{H'})=0となり，関数$ \mathrm{halt'}の定義より，$ \mathrm{halt'}(\widehat{H'})=1となる．しかし，これは，「$ H'が，入力$ \widehat{H'}に対して（1 を出力して）停止する」ことになる．
書き起こした。wint.icon
誤記
やっぱり図2.27, 28は間違ってるのでは？判定対象のプログラムの停止性で case分析するはず。
ref.