Нерешаемые задачи
| English | Русский |
|---|---|
| cannot/ˈkænɒt/ | невозможно |
| decidable/dɪˈsaɪdəbl/ | решаемый |
| undecidable/ˌʌndɪˈsaɪdəbl/ | нерешаемая проблема |
| limit/ˈlɪmɪt/ | предел |
| inefficient/ɪnɪˈfɪʃənt/ | неэффективна |
Не все задачи разрешимы
- Не каждую задачу можно решить с помощью компьютера, даже в теории.
- Чтобы понять почему, разделим задачи на два типа.
- Один тип компьютер всегда может решить; другой — нет.
- Это установленный факт информатики, а не пробел, который мы когда-нибудь заполним.
Решаемая задача — это одна, где:
"Четно ли число n?
Разрешимые задачи
- Разрешимая задача имеет алгоритм, который для каждого случая дает правильный ответ «да» или «нет».
- «Является ли это число четным?» — разрешима; простой тест всегда дает верный ответ.
- «Является ли это число простым?» — тоже разрешима, хотя и медленна для огромных чисел.
- Если для каждого случая существует правильный алгоритм, задача является разрешимой.
Решаемая или нерешаемая?
Решаемая задача имеет алгоритм, который всегда дает правильный ответ для каждого случая; нерешаемая задача не имеет такого алгоритма — она невозможна, а не просто медленна.
Нерешаемая задача:
Некоторые случаи неподвластны любой возможной программе.
Определение в общем случае, остановится ли когда-либо данная программа:
Ни один единый алгоритм не даст правильного ответа для каждой программы.
Неразрешимость обозначает строгую ⟦number⟧ на возможности вычислений.
Некоторые вопросы вообще не имеют общего алгоритма.
Неразрешимые задачи
- Неразрешимая задача не имеет алгоритма, способного правильно решить каждый случай.
- Как бы ни был изобретателен программа, некоторые случаи останутся ей недоступны.
- Классический пример: определение в общем случае, остановится ли какая-либо заданная программа.
- Неразрешимость — это предел того, что может достичь вычисление; некоторые вопросы просто не имеют общего алгоритма.
Нерешаемость и лишь неэффективность (медлительность) означают одно и то же.
Неэффективность можно решить медленно; нерешаемость невозможно решить ни для каких случаев в целом.
Проверка простоты числа является разрешимой, даже если это занимает много времени для огромных чисел.
Алгоритм всегда дает ответ; медленный — не то же самое, что невозможный.
Неразрешимость ≠ просто медленность
- Не путайте неразрешимость с простой неэффективностью.
- Неоптимальную задачу можно решить, но медленно. Неразрешимую же нельзя решить для каждого случая вообще.
Простые числа против остановки. Проверка простоты числа — разрешима: алгоритм всегда отвечает, хотя и медленно для огромных чисел. Но определение в общем случае, остановится ли любая программа, — неразрешимо: не существует единого алгоритма, который давал бы верный ответ для каждой программы. Медленно — не то же самое, что невозможно.
Для разрешимой задачи существует алгоритм, который всегда отвечает верно («четно ли n?», «простое ли n?»). Для неразрешимой такой алгоритм отсутствует для каждого случая (остановится ли программа?) — это реальный предел вычислений. Неразрешимость означает, что задачу невозможно решить, а не просто неэффективно (медленно).