Вопрос : Является ли прогнозирование (как определено ниже) вычислимых последовательностей столь же сложным, как проблема остановки?
Разработка : «Предсказать» означает успешное прогнозирование, что означает делать только конечное число ошибок при попытке прогнозирования n-го бита последовательности при доступе к предыдущим n-1 битам (начиная с первого бита и проходя через вся бесконечная вычислимая последовательность).
Существует простой аргумент диагонализации (из-за Legg 2006), что для любого предиктора машины Тьюринга p существует вычислимая последовательность, в которой он делает бесконечно много ошибок. (Создайте последовательность, которая имеет n-й член, противоположный тому, что предсказывает p, исходя из предыдущих n-1 членов в последовательности.) Таким образом, не существует вычислимого предиктора, который предсказывал бы каждую вычисляемую последовательность. Остановка оракула позволила бы построить такого предиктора. Но можете ли вы показать, что наличие такого предиктора позволяет решить проблему остановки?
Более детальная проработка
Определение (Legg)
. Предиктор p - это машина Тьюринга, которая пытается предсказать n-й бит последовательности S при доступе к предыдущим n-1 битам. Если прогноз не соответствует n-му биту последовательности, мы называем это ошибкой . Мы будем говорить, что p предсказывает S, если p делает только конечное число ошибок на S. Другими словами, p предсказывает S, если в последовательности st есть некоторое число M для каждого m> M, p правильно предсказывает m-й бит S предоставляется доступ к первым m-1 битам.
Формально мы можем определить машину предиктора как имеющую три ленты. Последовательность вводится как побитовая на одной ленте, предсказания для следующего бита делаются на второй ленте (машина может перемещаться только по этой ленте), а затем появляется рабочая лента, на которой машина может двигаться в обоих направлениях.
Простые результаты
По приведенному выше определению существует предиктор, который предсказывает все рациональные числа. (Используйте стандартное зигзагообразное перечисление рациональных чисел. Начните с предсказания 1-го рационального в списке, если есть ошибка, переходите к следующему рациональному.). По аналогичному аргументу есть предиктор, предоставляющий доступ к N, способный предсказать все последовательности сложности Коломогорова, меньшие или равные N. (Запустите все N-битные машины параллельно и сделайте прогноз машины, которая остановится первой Вы можете делать только конечное количество ошибок).
Цитирование Шейн Легг 2006 г. http://www.vetta.org/documents/IDSIA-12-06-1.pdf (не автор этого поста)