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

著者 : 高橋正子

• 近代科学社 (1991年8月1日発売)

感想・レビュー・書評

[岩手県立大学メディアセンターさんの感想 · 2023年7月1日]

＜シラバス掲載参考図書一覧は、図書館HPから確認できます＞
https://libipu.iwate-pu.ac.jp/drupal/ja/node/190

[disktnkさんの感想 · 2012年12月19日]

第1章は，代入・判定・入出力で構成されるNプログラムを厳密に拡張していき，計算可能性を検証する．ゲーデル数〜チューリング完全の解説ではあるが，原始的関数や帰納的関数，述語，決定可能集合とつながり，計算不可能についての概念が理解できる．
第2章はλ計算の概要．第1章のNプログラムとの関連付けが可能であり，λ式の計算可能性へとつなげる．公理系をβ・η・κと拡張していくことで何が言えるのかを押さえるのがポイント(だと思う)．
第3章は数学的構造をλ式で表すλ計算のモデルの話で，λモデルの計算可能性へと結んでいく．
いきなりユークリッド互除法が出てくるものの，あとは定義と証明の繰り返しで計算可能性を論じているので，1つ1つ丁寧に進めていけば初学者でもついていける構成(らしい)．しかし文中の問を独学で解くのは厳しく(本著には，一部の問にヒントがあるだけ)，またその問を使って次の定理へと進めていくので独学だと厳しいと思う．正直自分はあまりにも納得できない部分以外は読み飛ばした．とはいえ，λ式やλ計算論についての日本語の書籍は貴重であり，他の論文を読む上で非常に参考になる．
言うまでもなく内容はアカデミックであり，実務への応用はまたさらなる専門知識が必要．

[cota311さんの感想 · 2012年6月20日]

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

[kaizenさんの感想 · 2011年6月25日]

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

著者プロフィール

東工大名誉教授

「2016年 『コンピュータと数学』 で使われていた紹介文から引用しています。」