Есть проблемы, которые разрешимы, есть проблемы, которые неразрешимы, есть полурешимость и т. Д.
В этом случае мне интересно, может ли проблема быть мета неразрешимой. Это означает (по крайней мере, в моей голове), что мы не можем сказать, разрешимо это или нет.
Возможно, известно, что разрешимость неразрешима (все неразличимо с мета), и не существует алгоритма, который бы доказывал разрешимость чего бы то ни было, поэтому разрешимость должна быть доказана вручную в каждом конкретном случае.
Может быть, мой вопрос не имеет смысла. Может быть, я предполагаю, что мы - углеродные машины, использующие очень сложные алгоритмы, и поэтому вопрос имеет смысл только в моей голове.
Пожалуйста, дайте мне знать, если вопрос требует дальнейшего уточнения. Мне может понадобиться это сам в данный момент.
Спасибо.
Ответы:
Вот быстрый набросок, показывающий, что не существует машины Тьюринга, чтобы решить, разрешим ли произвольный класс проблем.
Я должен уточнить, что я имею в виду под классом проблем: классом проблемT является машиной Тьюринга, которая перечисляет элементы (скажем, натуральные числа) рекурсивно перечислимого множества один за другим, так что каждый элемент в наборе в конечном итоге печатается. Проблема интуитивно пойманаT( н ) это: "это число N в этом наборе? ". Это фиксирует обычные проблемы в области вычислимости, такие как" является ли я индексом машины Тьюринга, которая останавливается при пустом вводе? ".
Предположим, была машинаM который, учитывая в качестве входных данных класс проблем T ответил т т у й если этот класс разрешим и е L сек е в противном случае.
Теперь возьмите произвольную машину ТьюрингаT , Мы строим следующий класс задачT' следующим образом:
Теперь понятно, что еслиT затем останавливается M(T') возвращается е L сек е , так как множество показателей остановки машин Тьюринга не является разрешимым (рекурсивным) набором.
ЕслиT это не остановить, тоT' не перечисляет любые номера, что делает его именно класс задач , не содержащих ни одного индексов! СледовательноM(T') ответы т т у й , поскольку этот класс разрешим (на машине, которая всегда отклоняет).
Следовательно,M(T') возвращается т т у й тогда и только тогда T не останавливается, а е L сек е в противном случае. Таким образом, существованиеM позволяет нам решить проблему остановки для произвольной машины T , что является противоречием.
источник
Очень классная идея!
Идея: мы можем использовать аксиому понимания в теории множеств ZF для определения языка, который зависит от независимого утверждения.
Шаг 1: Примите ваше любимое утверждение, которое не зависит от ZF, например AC - аксиома выбора.
Шаг 2: Определите язык L = {x в {0,1} | x = 0, если AC, и x = 1, если не AC}. Обратите внимание, что L является либо {0}, либо {1}. Теперь L разрешима, но мы не можем с уверенностью предоставить программу, которая решает L. Мы могли бы предоставить программу, которая решает {0}, или мы могли бы предоставить программу, которая решает {1}, но мы не знаем наверняка который решает Л.
Шаг 3: Используйте эту идею, чтобы определить язык, который разрешим, если AC, и неразрешим, если НЕ AC. Пусть H будет множеством остановки, которое неразрешимо. Определить L = {x | x - строка, если AC, и x в H, если NOT AC}. Если AC, то L = множество всех строк и L разрешима. Если НЕ AC, то L = H и L неразрешима. Является ли L разрешимым, не зависит от ZF.
источник