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.
5.3
最大の能力
149
力を与えることは基本的に不可能なのです。
私たちはすでに、これが非決定性に当てはまることを見てきました。ここからは、その他の伝統的な
チューリングマシンの拡張（内部ストレージ、サブルーチン、複数のテープ、多次元のテープ）につい
て、なぜそれが計算能力を高めることにならないのか見ていきましょう。複雑なテクニックが必要なも
のもありますが、結局のところ、それらはプログラミングの問題にすぎません。
5.3.1
内部ストレージ
チューリングマシンには好きに使える内部ストレージがないため、規則集を設計するのに苦労しま
す。たとえば、テープヘッドをある位置に動かし、そこに格納されている文字を読み、それから別の位
置にヘッドを動かし、そして先ほど読んだ文字に依存したアクションを実行する、というのはよくある
動作です。ところが、チューリングマシンには文字を「覚えておく」手段がないため、一見するとこれ
は不可能なことのように思えます。もちろん、文字はテープに書かれているので、ヘッドをその位置に
戻すことで、好きなときに好きなだけその文字を読むことができますが、ヘッドがそのマス目を離れて
しまうと、もはやその内容に基づいて規則を実行することはできなくなります。
もしチューリングマシンに一時的な内部ストレージ（「RAM」、「レジスタ」、「ローカル変数」などと
呼ばれるもの）があれば、もっと便利でしょう。テープヘッドの下にある文字を内部ストレージに保存
しておけば、たとえヘッドが別の場所に動いても、あと
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.