Undecidable Problems
Введено| English | Значение |
|---|---|
| cannot/ˈkænɒt/ | не может |
| decidable/dɪˈsaɪdəbl/ | решаемый |
| undecidable/ˌʌndɪˈsaɪdəbl/ | нерешаемый |
| limit/ˈlɪmɪt/ | предел |
| inefficient/ɪnɪˈfɪʃənt/ | неэффективный |
Не все задачи разрешимы
- Не каждую задачу можно решить с помощью компьютера, даже в теории.
- Чтобы понять почему, разделим задачи на два типа.
- Один тип компьютер всегда может решить; другой — нет.
- Это установленный факт информатики, а не пробел, который мы когда-нибудь заполним.
A decidable problem is one where:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
"Is n even?" is decidable — always answerable.
Разрешимые задачи
- Разрешимая задача имеет алгоритм, который для каждого случая дает правильный ответ «да» или «нет».
- «Является ли это число четным?» — разрешима; простой тест всегда дает верный ответ.
- «Является ли это число простым?» — тоже разрешима, хотя и медленна для огромных чисел.
- Если для каждого случая существует правильный алгоритм, задача является разрешимой.

Решаемые и нерешаемые задачи
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.
Неразрешимые задачи
- Неразрешимая задача не имеет алгоритма, способного правильно решить каждый случай.
- Как бы ни был изобретателен программа, некоторые случаи останутся ей недоступны.
- Классический пример: определение в общем случае, остановится ли какая-либо заданная программа.
- Неразрешимость — это предел того, что может достичь вычисление; некоторые вопросы просто не имеют общего алгоритма.
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.
Неразрешимость ≠ просто медленность
- Не путайте неразрешимость с простой неэффективностью.
- Неоптимальную задачу можно решить, но медленно. Неразрешимую же нельзя решить для каждого случая вообще.
Простые числа против остановки. Проверка простоты числа — разрешима: алгоритм всегда отвечает, хотя и медленно для огромных чисел. Но определение в общем случае, остановится ли любая программа, — неразрешимо: не существует единого алгоритма, который давал бы верный ответ для каждой программы. Медленно — не то же самое, что невозможно.
Для разрешимой задачи существует алгоритм, который всегда отвечает верно («четно ли n?», «простое ли n?»). Для неразрешимой такой алгоритм отсутствует для каждого случая (остановится ли программа?) — это реальный предел вычислений. Неразрешимость означает, что задачу невозможно решить, а не просто неэффективно (медленно).