ラムダ計算とチューリングマシンの違い 2009-04-13 - きしだのはてな

ぼくもYコンビネータがわかるようになるまではそうだったのだけど、Yコンビネータを使うとどのような処理ができるのかがよくわからなくて悩んでいる人が多いように思う。他の人のブログを見ても、名前をつけずに再帰ができるのがすばらしいとか書いてあったりするのだけど、それによってどういう処理ができるのかわからずにいた。 結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。 結局、Yコンビネータによってどのような処理ができるかというのは、ラムダ計算の要素のメリットをチューリングマシンの中に見出そうとしてるといえる。 ラムダ計算とチューリングマシンは、どちらも計算モデルという点では一致しているけど、全く違う。 無限であるか有限かの違いといってもいい。 チューリングマシンでは、データの量と処理

[yoshidaa]

プログラムは、いかに手続きを実行するかという命令的な側面と、いかに手続きを記述するかという宣言的な側面がある。チューリングマシンは前者の基礎で、ラムダ計算は後者の基礎であるということになる。

[noopable]

まさにAgdaライクな。でも、この話ってチューリング宗教論争に発展しそうでちょっと怖いですが。

[xmx3]

ラムダ計算を基礎としてプログラムを考えていくことで、確実に動くプログラムを書くということを考えれるようになる。このようなことから、並列計算でのプログラム記述などに関数型言語が使われるようになっている。

[Nagise]

今、何かが見えた。

[twobit]

[computer]

[esper]

もいっかい読む

[rryu]

そしてプログラム意味論に話は繋がっていくという壮大なプロローグなのだろうか——

[nanakoso]

チャーチ的に等価なラムダ計算とチューリングマシンそれぞれ独自の存在意義

[o_show]

＞つまり、今プログラムを書くときに、「プログラムの書き方」といって「スコープはせまく」とか「型あり言語は実行時エラーがでにくい」とかいう話をしてるのは、その背景にはラムダ計算があるわけだ。

[ite]

面白かった。計算能力は等価でもアプローチの違いがこういった見え方の違いをもたらすんだな。

[chintaro3]

勉強になった

[tomoemon]

計算機科学/計算モデルっていろいろあるんだよなー。