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.
138
5
章 究極の機械
厳密に言うと、テープヘッドを最初の位置に戻す必要はありません。状態
2
を受理状態にする
と、機械は
0
を
1
に置き換えると即座に停止しますが、テープには正しい結果が含まれていま
す。テープヘッドを最初の位置に戻しているのは、現在の状態を状態
1
に戻すだけで機械を再
実行可能にするためです。この機械を何度も実行することで、テープに記録されている数を
繰り返しインクリメントできます。これはさらに大きな機械、たとえば
2
つの
2
進数の足し算
や掛け算の一部として再利用することができます。
5.1.2
規則
コンピュータによって実行される操作を、これ以上分割するのが困難な、基本的で「単純な操作」
に分割することを考えましょう。［……］実際に実行される操作は、［……］コンピュータ内部の状態
と観測されたシンボルによって決められます。具体的に言うと、これらの操作は、操作が実行され
た後のコンピュータ内部の状態を決めます。
これで、この
コンピュータの作業をする機械を構築できるようになります。
̶̶
アラン・チューリング「
On Computable Numbers, with an Application to the
Entscheidungsproblem
」
計算のステップごとに、チューリングマシンに実行させたい「単純な操作」があります（テープヘッ
ドの現在の位置にある文字を読む、その位置に新しい文字を書く、ヘッドを左右どちらかに動かす、
状態を変更する）。プッシュダウン・オートマトンでやったのと同じよう
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.