Undecidable Problems
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| cannot/ˈkænɒt/ | không thể |
| decidable/dɪˈsaɪdəbl/ | có thể quyết định được |
| undecidable/ˌʌndɪˈsaɪdəbl/ | không thể quyết định được |
| limit/ˈlɪmɪt/ | Giới hạn |
| inefficient/ɪnɪˈfɪʃənt/ | Kém hiệu quả |
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:
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
"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:
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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).