Я понимаю, что большинство проблем тривиальны, если доступен остановившийся оракул (или, я думаю, что эквивалентно, гипер-вычисления). Однако применение аргумента, который показывает проблему остановки, для машины Тьюринга также показывает, что для оракула Тьюринга невозможно решить проблему остановки для оракула Тьюринга. Существуют ли какие-либо реальные, практические примеры проблем, неразрешимых при остановке оракулом?
Примечание: под «оракулом» я подразумеваю оракула для стандартной машины Тьюринга, а не ТМ с самим оракулом.
Ответы:
Просто возьмите задачу, у которой степень Тьюринга выше , то есть степень Остановки Оракула. С точки зрения арифметической иерархии вы хотите проблемы, которые выше . Примеры таких задач (где - это частичная вычислимая функция, а - это - й вычислимо перечислимый набор):0′ Σ01 ϕn n Wn={k∈N∣ϕn(k) is defined} n
Ничто из этого не может быть решено, даже если у вас Оракул Остановки. Например, рассмотрим второй пример: "is total?" Учитывая , как бы помощь Приостановление Oracle нам решить , кодируются ли машина Тьюринга по привалов на каждом входе?φn n n
[Добавлено 2014-06-03] Для «практического» аспекта всего этого рассмотрим проблему: программист написал функцию,
void charge_credit_card(int card_number, int amount)
и мы хотели бы знать, завершается ли функция на всех входах. Это невозможно , чтобы написать компилятор , который может автоматически проверить это в целом. Более того, даже если мы позволим компилятору задавать нам вопросы вида «charge_credit_card
завершается ли при заданном вводе(k,m)
?», Это все равно невозможно.источник
int
, вполне очевидно. Вы действительно нуждаетесь во мне, чтобы написатьBigInt
или что-то подобное, или вы потом пожалуетесь, что память компьютера ограничена?