Undecidable Problems · 不可判定问题
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| cannot/ˈkænɒt/ | 不能 | bù néng |
| decidable/dɪˈsaɪdəbl/ | 可判定 | kě pàn dìng |
| undecidable/ˌʌndɪˈsaɪdəbl/ | 不可判定 | bù kě pàn dìng |
| limit/ˈlɪmɪt/ | 极限 | jí xiàn |
| inefficient/ɪnɪˈfɪʃənt/ | 低效 | dī xiào |
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. · "n 是偶数吗?"是可判定的——总能回答。
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)问题有一个算法,总为每个情况给出正确的是或否答案。
- "这个数是偶数吗?"是可判定的——一个简单测试总能正确回答。
- "这个数是素数吗?"也是可判定的,即使对巨大的数很慢。
- 如果对每个情况都存在一个正确的算法,问题就是可判定的。
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)问题没有正确解决每个情况的算法。
- 无论程序多聪明,一些情况都会难倒它。
- 经典例子:一般地判定任何给定的程序是否会停止运行。
- 不可判定性是计算所能达到的一个极限(limit)——一些问题就是没有通用算法。
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.
不可判定不只是慢
- 别把不可判定与仅仅低效(inefficient)混淆。
- 一个低效的问题能被解决,只是慢。一个不可判定的不能(cannot)对每个情况被解决。
素数与停机。 测试一个数是否为素数是可判定的——一个算法总能回答,即使对巨大的数很慢。但一般地判定任何程序是否会停机是不可判定的:没有单一算法对每个程序都正确回答。慢与不可能不是一回事。
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).
一个可判定问题有一个总能正确回答的算法("n 是偶数吗?"、"n 是素数吗?")。一个不可判定问题对每个情况没有这样的算法(一个程序会停机吗?)——计算的一个真正极限。不可判定意味着它根本不能被解决,而非仅仅低效(慢)。