Undecidable Problems
Introduced| English | Meaning |
|---|---|
| cannot/ˈkænɒt/ | cannot |
| decidable/dɪˈsaɪdəbl/ | decidable |
| undecidable/ˌʌndɪˈsaɪdəbl/ | Describes a decision problem for which no algorithm can always terminate with the correct yes/no answer for every possible input. |
| limit/ˈlɪmɪt/ | A value that a function or sequence approaches as its input or index approaches a specified value. |
| inefficient/ɪnɪˈfɪʃənt/ | inefficient |
Not every problem is solvable
- Not every problem can be solved by a computer, even in principle.
- To see why, we sort problems into two kinds.
- One kind a computer can always answer; the other it cannot.
- This is a proven fact of computer science, not a gap we might one day fill.
A decidable problem is one where:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
"Is n even?" is decidable — always answerable.
Decidable problems
- A decidable 可判定 problem has an algorithm that always gives a correct yes-or-no answer for every case.
- "Is this number even?" is decidable — a simple test always answers correctly.
- "Is this number prime?" is decidable too, even if slow for huge numbers.
- If a correct algorithm exists for every case, the problem is decidable.
Decidable and undecidable 不可判定 problems
Decidable or undecidable?
A decidable problem has an algorithm that always answers correctly for every case; an undecidable one has no such algorithm — being impossible, not merely slow.
An undecidable problem:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Some questions simply have no general algorithm.
Undecidable problems
- An undecidable problem has no algorithm that solves every case correctly.
- No matter how clever the program, some cases will defeat it.
- The classic example: deciding, in general, whether any given program will ever stop running.
- Undecidability is a limit 极限 on what computation can achieve — some questions simply have no general algorithm.
Undecidable and merely inefficient (slow) mean the same thing.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Inefficient can be solved slowly; undecidable cannot be solved for every case at all.
Testing whether a number is prime is undecidable because it can be slow for huge numbers.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
False. Primality is decidable: an algorithm always gives an answer. Being slow is not the same as being impossible.
Undecidable is not just slow
- Do not confuse undecidable with merely inefficient 低效.
- An inefficient problem can be solved, just slowly. An undecidable one cannot 不能 be solved for every case at all.
Prime vs halting. Testing whether a number is prime is decidable — an algorithm always answers, even if slow for huge numbers. But deciding in general whether any program will halt is undecidable: no single algorithm answers correctly for every program. Slow is not the same as impossible.
A decidable problem has an algorithm that always answers correctly ("is n even?", "is n prime?"). An undecidable problem has no such algorithm for every case (will a program halt?) — a real limit of computing. Undecidable means it cannot be solved at all, not merely inefficient (slow).