計算論 計算可能性とラムダ計算 コンピュータサイエンス大学講座24

高橋正子【著】

• 販売会社／発売会社: 近代科学社
• 発売年月日: 1991/08/30
• JAN: 9784764901841

商品レビュー

2012/06/20

この分野の日本語の本は少ないので、とてもありがたい。分量が少なく、その分、行間が少し開き気味の書き方になっているので、そこを自分で埋められれば、より勉強になるだろう。

2011/06/25

最初に割り算と引き算について、自然数で閉じるように定義をしている。
次ぎに、ユークリッドの互除法の原理の説明がある。
gcd(x,y) = gcd(y,mod(x,y)) if (y>0)
= x (y=0)
いきなりmod関数を使っている。
１．６計算不可能な関数と決定不能な問題で、
「帰納的述語ではない」ということと、計算不可能という関係がよくわからなかった。
決定不能な問題としては、Postの対応問題、Hilbertの第１０問題の紹介があるが、証明は省略されている。参考文献として、廣瀬健の帰納的関数が参考文献にある。