В теории вычислимости и теории вычислительной сложности неразрешимая проблема — это проблема решения, для которой доказано, что невозможно построить алгоритм , который всегда приводит к правильному ответу «да» или «нет». Примером может служить проблема остановки : можно доказать, что не существует алгоритма, который правильно определяет, останавливаются ли в конечном итоге произвольные программы при запуске.
Проблема принятия решения — это любой произвольный вопрос, на который можно ответить «да» или «нет», на бесконечном наборе входных данных. Из-за этого традиционно проблему принятия решения эквивалентно определяют как набор входных данных, для которых задача возвращает « да » . Эти входные данные могут быть натуральными числами, а также другими значениями, такими как строки формального языка . Используя некоторую кодировку, такую как нумерация Гёделя , строки могут быть закодированы как натуральные числа. Таким образом, проблема решения, неформально сформулированная в терминах формального языка, также эквивалентна набору натуральных чисел . Чтобы упростить формальное определение, оно сформулировано в терминах подмножеств натуральных чисел.
Формально задача решения — это подмножество натуральных чисел. Соответствующая неформальная проблема состоит в том, чтобы определить, входит ли заданное число в множество. Задача решения A называется разрешимой или эффективно разрешимой, если A — рекурсивное множество, и неразрешимой в противном случае. Задача называется частично разрешимой, полуразрешимой, разрешимой или доказуемой, если A — рекурсивно перечислимое множество . [1]
Алан Тьюринг доказал в 1936 году, что общего алгоритма, работающего на машине Тьюринга, который решает проблему остановки для всех возможных пар программа-ввод, обязательно не может существовать. Следовательно, проблема остановки неразрешима для машин Тьюринга.
Понятия, выдвинутые теоремами Гёделя о неполноте , очень похожи на те, которые возникают в связи с проблемой остановки, и доказательства очень похожи. Фактически, более слабая форма первой теоремы о неполноте является простым следствием неразрешимости проблемы остановки. Эта более слабая форма отличается от стандартной формулировки теоремы о неполноте тем, что утверждает, что аксиоматизация натуральных чисел, которая была бы полной и надежной , невозможна. «Надежная» часть — это ослабление: это означает, что мы требуем, чтобы рассматриваемая аксиоматическая система доказывала только истинные утверждения о натуральных числах. Поскольку надежность подразумевает постоянство , эту более слабую форму можно рассматривать как следствиесильной формы. Важно отметить, что утверждение стандартной формы первой теоремы Гёделя о неполноте совершенно не касается истинности утверждения, а касается только вопроса о том, можно ли найти его с помощью математического доказательства .