チューリング機械を学ぶ
気を抜いたら前回の投稿から2ヶ月も開いてしまった。その間色々あったような気もするけど、とりあえず今思いついてることをメモしておこう。
最近はLisp熱が再燃している。そしてそれと同時にそろそろこの先自分がどういう分野を勉強しようか、それを考える足がかりとしてチューリング機械について学び直している。
(ちなみに今は計算複雑性理論を学びたいなーなんて漠然と考えている)
チューリング機械についての簡単なことは随分前からwikipediaなんかで読んだこともあったし本で目にすることもあった。それどころか昨きちんと大学の授業の中で勉強する機会もあった。
しかしやはり表層的な理解しかしていないのではないかと薄々感じてはいた。
そこで偶然図書館でこの本をみかけたのでとりあえず読んで見ることにした。
いや正直なところをいうと実は勘違いして本来とは別の本を借りてしまったのだ。
当初借りる予定だった本はこちら。
Amazonのオススメか何かでよくみかけていた。
しかし今になって見てみると後者はあまり評判が良くなく、前者の方がレビューは高評価だったのでまぁいいかと思っている。とりあえず、「チューリングを読む」を読み終えたらこちらも借りてみようかと思っている。
これと並行してLisp、SBCLでのCommon Lispの勉強もしている。
今回はそんな中思いついたことをいくつかメモしておこうと思って投稿を書いている。
[その1]
Lispにおいてプログラムとはデータである、という文言をよくみかけるけど今までよくわからなかった。
とりあえずシングルクオートがそれを直観的に理解する分かりやすい例だと今は思っている。
本当はS式の仕組みだとかマクロだとかのことかもしれないが、ともかくぼくにはそう感じた。
[その2]
チューリング完全の性質には「自己記述が可能である」が含まれている？
でも自己記述とは2種類あるのではないか
1.自己複製
要するにクワイン、自己増殖をするプログラムのこと。
現実ではウイルスとか。ニコニコ動画のライフゲーム動画の最後にあった。
2.自己言及
フラクタルみたいな。枠組みそのものをコピーする。
Lisp上でのLispの実装とか、ライフゲームの中でライフゲームとか。
前者はある体系の中で自己言及を行うオブジェクトが記述できるという話。
しかし後者はある体系そのものを自己言及し、再現することが可能という話。
枠組みの段階、というかメタ度(？)が異なっている。
GBE本に再挑戦する必要があるのだろうか。
[その3]
色々な文章で既に書かれているが、Lispはことこのチューリング機械にかんする話題と親和性が高いらしい。
それはやはりLispがメタプログラミングしやすいという特徴からきているのだろうか。
なぜLispなのか？ そこをもう少し知りたいと思う。
ps.
Lispの勉強法をゆるく募集している。
とりあえずりりかる☆Lispを終えて、はじめての人のためのLispを途中まで読んでいる。
でもはじめての〜は途中でわけがわからなくなって投げてしまった。
再入門には何が良いだろうか？
他の言語に比べれば数は少ないが、それでも入門書はある。
問題は、またそれらを読んでも挫折するんじゃないかという点だ。
プログラミングの本は安くないのでできれば入門書は一冊に留めたいところ。
2013/1/8 追記
タイトル脱字を修正
最近はLisp熱が再燃している。そしてそれと同時にそろそろこの先自分がどういう分野を勉強しようか、それを考える足がかりとしてチューリング機械について学び直している。
(ちなみに今は計算複雑性理論を学びたいなーなんて漠然と考えている)
チューリング機械についての簡単なことは随分前からwikipediaなんかで読んだこともあったし本で目にすることもあった。それどころか昨きちんと大学の授業の中で勉強する機会もあった。
しかしやはり表層的な理解しかしていないのではないかと薄々感じてはいた。
そこで偶然図書館でこの本をみかけたのでとりあえず読んで見ることにした。
いや正直なところをいうと実は勘違いして本来とは別の本を借りてしまったのだ。
当初借りる予定だった本はこちら。
Amazonのオススメか何かでよくみかけていた。
しかし今になって見てみると後者はあまり評判が良くなく、前者の方がレビューは高評価だったのでまぁいいかと思っている。とりあえず、「チューリングを読む」を読み終えたらこちらも借りてみようかと思っている。
これと並行してLisp、SBCLでのCommon Lispの勉強もしている。
今回はそんな中思いついたことをいくつかメモしておこうと思って投稿を書いている。
[その1]
Lispにおいてプログラムとはデータである、という文言をよくみかけるけど今までよくわからなかった。
とりあえずシングルクオートがそれを直観的に理解する分かりやすい例だと今は思っている。
本当はS式の仕組みだとかマクロだとかのことかもしれないが、ともかくぼくにはそう感じた。
[その2]
チューリング完全の性質には「自己記述が可能である」が含まれている？
でも自己記述とは2種類あるのではないか
1.自己複製
要するにクワイン、自己増殖をするプログラムのこと。
現実ではウイルスとか。ニコニコ動画のライフゲーム動画の最後にあった。
2.自己言及
フラクタルみたいな。枠組みそのものをコピーする。
Lisp上でのLispの実装とか、ライフゲームの中でライフゲームとか。
前者はある体系の中で自己言及を行うオブジェクトが記述できるという話。
しかし後者はある体系そのものを自己言及し、再現することが可能という話。
枠組みの段階、というかメタ度(？)が異なっている。
GBE本に再挑戦する必要があるのだろうか。
[その3]
色々な文章で既に書かれているが、Lispはことこのチューリング機械にかんする話題と親和性が高いらしい。
それはやはりLispがメタプログラミングしやすいという特徴からきているのだろうか。
なぜLispなのか？ そこをもう少し知りたいと思う。
ps.
Lispの勉強法をゆるく募集している。
とりあえずりりかる☆Lispを終えて、はじめての人のためのLispを途中まで読んでいる。
でもはじめての〜は途中でわけがわからなくなって投げてしまった。
再入門には何が良いだろうか？
他の言語に比べれば数は少ないが、それでも入門書はある。
問題は、またそれらを読んでも挫折するんじゃないかという点だ。
プログラミングの本は安くないのでできれば入門書は一冊に留めたいところ。
2013/1/8 追記
タイトル脱字を修正
