<< LISPで連番文字列 | top | ラムダ計算 >>

スポンサーサイト

一定期間更新がないため広告を表示しています

スポンサードリンク | - | | - | - |

計算可能とはどういうことか

少し前に購入した「計算論 計算可能性とラムダ計算」(高橋正子著)の第一章を流し読みした。

計算可能とはどういうことなのか少しずつわかってきた。
内容を簡単にまとめておく。

1.1節ではNプログラムというものが定義される。
これは入力、代入、判定、出力からなる有限の有向グラフであり、よくプログラムを書くときに使われるフローチャートをシンプルにしたようなものだ。
1.2節ではwhileプログラムというものが定義される。これはC言語などの手続き型言語をシンプルにしたもので、input、if〜then〜、do while、outputから成る。
定理1.2.1でNプログラムとwhileプログラムは同等の計算能力を持つことが示される。

1.3節からが本番という感じで、原始帰納的関数というものについて述べられる。
これは初期関数zero()=0、suc(x)=x+1、p_ni(x_1・・・xn)=xiと関数の合成、再帰的定義によって構成される関数だ。
原始帰納的関数はNプログラムで計算可能であることが示される。
しかしNプログラムでは計算可能であるが原始帰納的関数でない例があるため、1.4節で拡張される。
これが帰納的関数で基本は原始帰納的関数であるが、原始的述語の最小解を求める操作が許される。
「Nプログラムによって計算可能な関数」と「帰納的関数」は一致することが示される。

1.5節ではチューリングマシンについて述べられ、これもまたNプログラムの計算能力と一致することが示される。このように種々の計算モデルがあるが、どれも本質的にNプログラムの計算能力を超えない。
より強力な計算モデルは存在しないのであろうと考えられているとのことである。

つまり、実質的に帰納的関数こそが計算可能な関数のすべてであろう、ということだね。
1.6節と1.7節については今のところあまり興味を惹かれないのでスルー。

この本、証明もきっちり書いてあるが読みやすい。証明部分はほとんど飛ばしたけど。面白いのでおすすめ。
 
ジャジャガッチ | LISP | 09:05 | comments(0) | trackbacks(0) |

スポンサーサイト

スポンサードリンク | - | 09:05 | - | - |
Comment









Trackback
URL:

07
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH