『計算モデルとプログラミング』
『計算モデルとプログラミング』
森北出版
誤読 wint.icon
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'}に対して停止しない」ことになる．
ここから変わった？wint.icon
てか これは なんだ？
一方，$ H'が$ \widehat{H'}に対して停止しないとすると，関数$ \mathrm{halt}の定義より，$ \mathrm{halt}(\widehat{H'},\widehat{H'})=0となる．さらに，関数$ \mathrm{halt'}の定義より，$ \mathrm{halt'}(\widehat{H'})=1となる．このことから，「$ H'が$ \widehat{H'}を入力としたときに（1 を出力して）停止する」ことになる．
一方，「$ 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分析するはず。