September 2014
Intermediate to advanced
336 pages
7h 53m
Japanese
Content preview from アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
不可能なプログラム
253
8
章
不可能なプログラム
私が思うに、この世で最も慈悲深いことは、
人間が脳裏にあるものすべてを関連づけられずにいることだろう。
—— H. P. ラヴクラフト（H. P. Lovecraft）
†
これまで、さまざまなコンピュータとプログラミング言語のモデルについて調べてきました。抽象機
械にはいろいろな種類があり、一部の機械は他の機械よりも高い能力を備えていました。なかでも非
常に明らかな制限のある機械が2種類ありました。有限オートマトンには、文字列の括弧のバランスが
とれているかどうか判定するといった、無限の数え上げを必要とする問題を解くことができません。
プッシュダウン・オートマトンには、文字列が文字
a
、
b
、
c
を同じ数だけ含んでいるかどうか判定する
といった、情報を複数の場所で再利用する必要のある問題を扱うことができません。
これに対して、これまで見てきた最も高度な装置であるチューリングマシンは、必要なものをすべて
備えているように見えます。任意の順にアクセスできる無限のストレージ、任意のループ、条件分岐、
サブルーチンを備えています。６章で見た極めて最小限のプログラミング言語、ラムダ計算も驚くほど
強力でした。創意工夫することで、単純な値と複雑なデータ構造を純粋なコードとして表現でき、そ
れらの表現を操るための操作を実装することができます。また７章では、ラムダ計算をはじめとする単
純なシステムが、チューリングマシンと同じだけの万能な能力を持っていることを見ました。
こうしたシ
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.