| English | 释义 | 拼音 |
|---|---|---|
| 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 |
并非每个问题都可解
- 并非每个问题都能被计算机解决,即使在原则上。
- 为看清原因,我们把问题分成两类。
- 一类计算机总能回答;另一类它不能。
- 这是计算机科学的一个已证明的事实,不是我们某天会填补的空缺。
A decidable problem is one where:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
"Is n even?" is decidable — always answerable.
可判定问题
- 一个可判定(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:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Some questions simply have no general algorithm.
不可判定问题
- 不可判定 问题没有能正确解决所有情况的算法。
- 无论程序多聪明,一些情况都会难倒它。
- 经典例子:一般地判定任何给定的程序是否会停止运行。
- 不可判定性是计算所能达到的一个极限(limit)——一些问题就是没有通用算法。
Undecidable and merely inefficient (slow) mean the same thing.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
False. Primality is decidable: an algorithm always gives an answer. Being slow is not the same as being impossible.
不可判定不只是慢
- 别把不可判定与仅仅低效(inefficient)混淆。
- 一个低效的问题能被解决,只是慢。一个不可判定的不能(cannot)对每个情况被解决。
素数与停机。 测试一个数是否为素数是可判定的——一个算法总能回答,即使对巨大的数很慢。但一般地判定任何程序是否会停机是不可判定的:没有单一算法对每个程序都正确回答。慢与不可能不是一回事。
一个可判定问题有一个总能正确回答的算法("n 是偶数吗?"、"n 是素数吗?")。一个不可判定问题对每个情况没有这样的算法(一个程序会停机吗?)——计算的一个真正极限。不可判定意味着它根本不能被解决,而非仅仅低效(慢)。