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

著者 :
  • 近代科学社
3.63
  • (5)
  • (2)
  • (12)
  • (0)
  • (0)
本棚登録 : 92
レビュー : 4
  • Amazon.co.jp ・本 (191ページ)
  • / ISBN・EAN: 9784764901841

感想・レビュー・書評

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

  • PL05 コンピュータ言語論
    CSC05F 計算理論
    数学とコンピュータ特集

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

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

全4件中 1 - 4件を表示

著者プロフィール

東工大名誉教授

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

高橋正子の作品

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)を本棚に登録しているひと

ツイートする