| English | 意味 |
|---|---|
| cannot/ˈkænɒt/ | できない |
| decidable/dɪˈsaɪdəbl/ | 判定可能 |
| undecidable/ˌʌndɪˈsaɪdəbl/ | 判定不可 |
| limit/ˈlɪmɪt/ | 限界 |
| inefficient/ɪnɪˈfɪʃənt/ | 非効率的 |
全ての問題が解けるわけではない
- 原理としても、コンピュータによって全ての問題が解決できるわけではありません。
- なぜそうなのかを理解するために、問題を2つの種類に分類します。
- コンピュータが常に答えられる一種と、それできない一種です。
- これは将来埋められるかもしれない欠落ではなく、計算機科学における証明された事実です。
判定可能な問題は以下のいずれの場合です：
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
"n は偶数か？" は判定可能であり、常に回答可能です。
判定可能な問題
- **判定可能（decidable）**な問題は、すべてのケースに対して常に正しいはい/いいえの答えを与えるアルゴリズムが存在します。
- 「この数は偶数か？」は判定可能です — 単純なテストで常に正しく答えます。
- 「この数は素数か？」もまた判定可能ですが、巨大な数に対しては遅い場合があります。
- すべてのケースに対して正しいアルゴリズムが存在する場合、その問題は判定可能です。
判定可能か判定不能か？
判定可能な問題は、すべてのケースで常に正しく答えるアルゴリズムが存在する問題であり、判定不能問題はそんなアルゴリズムが存在しない問題です。単に遅いだけでなく、本質的に不可能です。
判定不能問題とは：
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
いくつかのケースはあらゆるプログラムを破綻させる。
任意のプログラムが最終的に停止するかを一般に判断することは：
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
すべてのプログラムに対してこれに正しく答える単一のアルゴリズムは存在しない。
判定不能性は計算が可能とする thing に厳格な ______ を設けます。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
一部の質問には一般的なアルゴリズム自体が存在しません。
判定不可能な問題
- **判定不可能（undecidable）**な問題は、すべてのケースを正しく解決するアルゴリズムが存在しません。
- プログラムがいかに巧妙であっても、いくつかのケースはそれを破ります。
- 古典的な例：任意のプログラムがいつか実行を停止するかを一般的に決定すること。
- 判定不可能性は、計算が達成できることの限界であり、一部の質問には一般的なアルゴリズムが存在しない simply です。
「判定不能」は「単に非効率（遅い）」と同じ意味ではない。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
非効率的な問題は遅くても解決可能ですが、判定不能問題はすべてのケースで解決できません。
素数かどうかをテストすることは判定可能であり、巨大な数字では遅くても構いません。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
アルゴリズムは常に回答しますが、遅いことは不可能と同一ではありません。
判定不可能は単なる遅さではない
- 判定不可能性と単に非効率的であることを混同しないでください。
- 非効率的な問題は解くことができますが、ただ遅いです。一方、判定不可能な問題はすべてのケースにおいて根本的に解くことができません。
素数判定 vs 停止判定。 ある数が素数かどうかをテストすることは判定可能です — 巨大な数に対しては遅くても、アルゴリズムは常に答えます。しかし、任意のプログラムが停止するかを一般的に決定することは判定不可能です — どのプログラムでも正しく答える単一のアルゴリズムはありません。遅いことは不可能と同じではありません。
判定可能（decidable）な問題は、常に正しく答えるアルゴリズムがあります（「n は偶数か？」「n は素数か？」）。一方、判定不可能（undecidable）な問題は、すべてのケースに対してそのようなアルゴリズムが存在しません（プログラムは停止するか？）— これは計算の真の限界です。判定不可能とは、単に非効率的（遅い）というだけでなく、根本的に解くことができないことを意味します。