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.
254
8
章 不可能なプログラム
8.1
厳然たる事実
これらはかなり深い質問なので、取り掛かる前に計算の世界にある根本的事実について確認してお
きましょう。明らかなものもあれば、そうでないものもありますが、計算する機械の能力と制限につい
て考える上で、すべて重要な要件になります。
8.1.1
万能システムはアルゴリズムを実行できる
一般的に言って、チューリングマシンやラムダ計算、部分再帰関数といった万能システムを使うと、
何ができるのでしょうか。これら万能システムの能力を正しく理解できれば、その限界もわかるでしょ
う。
計算する機械の実用的な目的は、アルゴリズム（algorithm）を実行することです。アルゴリズムと
は、入力値を出力値に変えるプロセスを記述した命令のリストであり、以下の基準を満たしているもの
を指します。
有限性（Finiteness）
命令は有限個である。
単純性（Simplicity）
各命令は創意工夫しなくても、人が紙と鉛筆で実行できるくらい単純である。
停止性（Termination）
命令にしたがう人が、任意の入力について有限回のステップで
終わらせることができる。
正確性（Correctness）
命令にしたがう人が、任意の入力について正しい答えを生成することができる。
たとえば、最古として知られるアルゴリズムの1つに、紀元前300年ぐらいまでさかのぼったユーク
リッドのアルゴリズムがあります。このアルゴリズムは2 つの正の整数を受け取って、それら両方の数
を割り切れる最大の整数、すなわち
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.