Undecidable Problems
Introduced| English |
|---|
| cannot/ˈkænɒt/ |
| decidable/dɪˈsaɪdəbl/ |
| undecidable/ˌʌndɪˈsaɪdəbl/ |
| limit/ˈlɪmɪt/ |
| inefficient/ɪnɪˈfɪʃənt/ |
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:
"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 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:
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
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.
Inefficient can be solved slowly; undecidable cannot be solved for every case at all.
Testing whether a number is prime is decidable, even if it is slow for huge numbers.
An algorithm always answers; slow is not the same as 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).