Существуют ли какие-либо проблемы, которые невозможно решить с помощью оракула?

11

Я понимаю, что большинство проблем тривиальны, если доступен остановившийся оракул (или, я думаю, что эквивалентно, гипер-вычисления). Однако применение аргумента, который показывает проблему остановки, для машины Тьюринга также показывает, что для оракула Тьюринга невозможно решить проблему остановки для оракула Тьюринга. Существуют ли какие-либо реальные, практические примеры проблем, неразрешимых при остановке оракулом?

Примечание: под «оракулом» я подразумеваю оракула для стандартной машины Тьюринга, а не ТМ с самим оракулом.

Айк
источник
2
Там являются «произвольно неразрешимые» проблемы, см , например , здесь . Я не знаю о «практических» примерах (что также не соответствует названию, которое вы выбрали); что квалифицируется как «практическое» для вас?
Рафаэль
Это не выдумано, чтобы просто ответить на этот вопрос. Я признал, что проблема остановки следующего уровня по-прежнему актуальна.
IKE
Кроме того, все языки, которые не являются рекурсивно перечислимыми, не сводятся к HALT. Примеры включают в себя FINITE, EMPTY, один и тот же язык для двух CFG и т. Д.

Ответы:

15

Просто возьмите задачу, у которой степень Тьюринга выше , то есть степень Остановки Оракула. С точки зрения арифметической иерархии вы хотите проблемы, которые выше . Примеры таких задач (где - это частичная вычислимая функция, а - это - й вычислимо перечислимый набор):0Σ10ϕnnWn={kNϕn(k) is defined}n

  • {nNφn terminates for finitely many inputs} является -полным.Σ20
  • {nNφn is a total function} является -полным.Π20
  • {nNWn is a computable set} - .Σ30

Ничто из этого не может быть решено, даже если у вас Оракул Остановки. Например, рассмотрим второй пример: "is total?" Учитывая , как бы помощь Приостановление Oracle нам решить , кодируются ли машина Тьюринга по привалов на каждом входе?φnnn


[Добавлено 2014-06-03] Для «практического» аспекта всего этого рассмотрим проблему: программист написал функцию, void charge_credit_card(int card_number, int amount)и мы хотели бы знать, завершается ли функция на всех входах. Это невозможно , чтобы написать компилятор , который может автоматически проверить это в целом. Более того, даже если мы позволим компилятору задавать нам вопросы вида « charge_credit_cardзавершается ли при заданном вводе (k,m)?», Это все равно невозможно.

Андрей Бауэр
источник
2
Сказать «я не понимаю пример», не объяснив, что вас смущает, бесполезно. Вы читали соответствующие страницы Википедии, на которые я указал? Они имеют прямое отношение к вашему вопросу, поэтому первое, что вы должны сделать, это ознакомиться с основными понятиями.
Андрей Бауэр
1
@ike, пример должен был иметь бесконечное количество int, вполне очевидно. Вы действительно нуждаетесь во мне, чтобы написать BigIntили что-то подобное, или вы потом пожалуетесь, что память компьютера ограничена?
Андрей Бауэр
1
Без разницы. Я сказал вам, каков был ответ на ваш вопрос. Если вы не хотите понять это добросовестно, не беспокойте нас вопросами.
Андрей Бауэр
2
Практическим примером является , комплимент halt. Это Учитывая произвольную программу и ввод в программу, определите, не останавливается ли программа. Эта проблема, как и любой другой нерекурсивно перечислимый язык, не сводится к HALT. HALT¯{<M,w>:M doesn't halt on w}
1
@tAllan: вы должны опубликовать это как ответ. Это лучше, чем то, что ОП считает «практичным», но ваш пример, безусловно, лучше моего.
Андрей Бауэр