Возможна ли мета-неразрешимость?

9

Есть проблемы, которые разрешимы, есть проблемы, которые неразрешимы, есть полурешимость и т. Д.

В этом случае мне интересно, может ли проблема быть мета неразрешимой. Это означает (по крайней мере, в моей голове), что мы не можем сказать, разрешимо это или нет.

Возможно, известно, что разрешимость неразрешима (все неразличимо с мета), и не существует алгоритма, который бы доказывал разрешимость чего бы то ни было, поэтому разрешимость должна быть доказана вручную в каждом конкретном случае.

Может быть, мой вопрос не имеет смысла. Может быть, я предполагаю, что мы - углеродные машины, использующие очень сложные алгоритмы, и поэтому вопрос имеет смысл только в моей голове.

Пожалуйста, дайте мне знать, если вопрос требует дальнейшего уточнения. Мне может понадобиться это сам в данный момент.

Спасибо.

Trylks
источник
Рассмотрим утверждение «монадическая (второго порядка) теория всех линейных порядков вычислима». Есть основания полагать (но я не уверен, что независимость доказана), что это утверждение является независимым (то есть неразрешимым) в ZFC. Более подробную информацию о причинах можно найти в books.google.es/books?id=y3YpdW-sbFsC&pg=PA397
бумол
1
Когда вы говорите «разрешимость неразрешима», каков вход?
Махди Черагчи
2
Он также может быть заинтересован в en.wikipedia.org/wiki/Turing_degree, но неясно, как сформулирован вопрос. :)
Даниэль Апон
1
@boumol Shelah («Монадическая теория порядка», Ann. Math. 102 (3), 1975) доказал (предполагая CH), что «монадическая теория порядка неразрешима» (Теорема 7 (B), стр. 409).
Юваль Фильмус
1
Lзнак равно{проблема остановкиесли гипотеза континуума вернав противном случае
sdcvvc

Ответы:

8

Вот быстрый набросок, показывающий, что не существует машины Тьюринга, чтобы решить, разрешим ли произвольный класс проблем.

Я должен уточнить, что я имею в виду под классом проблем: классом проблем Tявляется машиной Тьюринга, которая перечисляет элементы (скажем, натуральные числа) рекурсивно перечислимого множества один за другим, так что каждый элемент в наборе в конечном итоге печатается. Проблема интуитивно пойманаT(N) это: "это число N в этом наборе? ". Это фиксирует обычные проблемы в области вычислимости, такие как" является ли я индексом машины Тьюринга, которая останавливается при пустом вводе? ".

Предположим, была машина M который, учитывая в качестве входных данных класс проблем T ответил TрUе если этот класс разрешим и еaLsе в противном случае.

Теперь возьмите произвольную машину Тьюринга T, Мы строим следующий класс задачT' следующим образом:

  1. Имитировать T,
  2. Если T halts, перечислять индексы машин Тьюринга, которые останавливаются при пустом вводе.

Теперь понятно, что если T затем останавливается M(T') возвращается еaLsе, так как множество показателей остановки машин Тьюринга не является разрешимым (рекурсивным) набором.

Если Tэто не остановить, тоT'не перечисляет любые номера, что делает его именно класс задач , не содержащих ни одного индексов! СледовательноM(T') ответы TрUе, поскольку этот класс разрешим (на машине, которая всегда отклоняет).

Следовательно, M(T') возвращается TрUе тогда и только тогда T не останавливается, а еaLsев противном случае. Таким образом, существованиеM позволяет нам решить проблему остановки для произвольной машины T, что является противоречием.

Коди
источник
Привет, Коди! Надеюсь, у тебя все хорошо. Будете ли вы в Питтсбурге этим летом?
Майкл Вехар
Привет! Я не уверен. Отправьте мне письмо, хотя!
Коди
1

Очень классная идея!

Идея: мы можем использовать аксиому понимания в теории множеств 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.

Майкл Вехар
источник