Как можно решить, имеет ли некоторую последовательность цифр?

Нам дали следующее упражнение.

Позволять

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Докажите, что вычислимо.$f$

Как это возможно? Насколько я знаю, мы не знаем, содержит ли каждую последовательность цифр (или какую), и алгоритм определенно не может решить, что какая-то последовательность не встречается. Поэтому я думаю, что не вычислимо, потому что основная проблема только разрешима.$\pi$$f$

Есть только две возможности для рассмотрения.

• Для каждого положительного целого числа строка появляется в десятичном представлении . В этом случае алгоритм, который всегда возвращает 1, всегда верен.$n$$0^n$$\pi$

• Существует наибольшее целое число такое, что появляется в десятичном представлении . В этом случае следующий алгоритм (со значением жестко запрограммирован) всегда корректен:$N$$0^N$$\pi$$N$

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

Мы понятия не имеем, какая из этих возможностей является правильной или какое значение является правильным во втором случае. Тем не менее, один из этих алгоритмов гарантированно будет правильным. Таким образом, существует алгоритм, позволяющий решить, появляется ли строка из нулей в ; проблема разрешима$N$$n$$\pi$

Обратите внимание на небольшую разницу со следующим эскизом, предложенным Галле :

1. Возьмите случайную машину Тьюринга и случайный вход.
2. Либо вычисления будут продолжаться вечно, либо остановятся в какой-то момент, и есть (постоянная) вычислимая функция, описывающая каждое из этих поведений.
3. ???
4. Прибыль!

Алекс тен Бринк объясняет:

обратите внимание на то, что гласит теорема Халтинга: в нем говорится, что не существует единой программы, которая могла бы решить, останавливается ли данная программа. Вы можете легко сделать две программы такими, чтобы одна из них вычисляла, останавливается ли данная программа: первая всегда говорит «она останавливается», вторая «она не останавливается» - одна программа всегда права, мы просто не можем вычислить, какая из них из них есть!

sepp2k добавляет:

В случае примера Алекса ни один из алгоритмов не вернет правильный результат для всех входных данных. В случае этого вопроса один из них будет. Вы можете утверждать, что проблема разрешима, потому что вы знаете, что существует алгоритм, который дает правильный результат для всех входных данных. Неважно, знаете ли вы, что это за алгоритм. 10

Просто опубликовать небольшую детализацию ответа Джеффа.

Мы знаем, что существуют две функции / случаи, которые могут вычислить функцию f (n):

1. Функция, которая всегда возвращает истину (для всех n существует n чисел подряд 0)
2. Функция, которая будет возвращать истину, если n меньше целого числа N, где N определяется как максимальная длина последовательных 0, которые существуют в данном иррациональном числе (в противном случае она возвращает ложь).

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

Количество шагов в случае 1 тривиально связано с просто возвращением 1.

В случае 2 количество шагов также конечно. Для каждого целого числа мы можем построить машину Тьюринга которая принимает, если и иным образом отклоняет ее за конечное время. Так что незнание верхней границы не имеет значения. Для каждого существует машина Тьюринга, а именно , которая правильно вычисляет, является ли (мы не знаем, какие из них являются правильными, но это не имеет значения, существует один).$N$$T_N(n)$$n < N$$N$$N$$T_N(n)$$n < N$

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

В качестве примечания: наше решение предполагает, что, хотя мы не можем определить, какая функция будет вызывать правильное значение, суть вычислимости не зависит от конструктивности доказательства. Чистого Существования достаточно.

Шаг 5 следующего доказательство попытки неоправданный, и на самом деле неправильно - контрпример можно найти здесь . (спасибо, Юваль; это было похоже на самую скудную часть наброска). Я оставил здесь ответ, так как считаю ошибку поучительной.

Во-первых: пары ответов Джеффа достаточно; f вычислима в любом случае.

Краткий обход, однако, в попытке сделать набросок доказательства по индукции:
предпосылка R : не повторяется. 1. Посмотрите на в базе 2. Это в основном для сокращения количества дел. 2. Независимо от того , как далеко вниз по линии вы идете, вы всегда найдете еще 1 где: альтернатива не все нули, которые означают , что начинает повторять, что идет вразрез с R . 3. То же самое касается перехода по линии и нахождения 0 . 4. Разверните до двузначных последовательностей: вы не можете перестать находить 01 или 10 (то есть места, где он переключается), потому что иначе$\pi$
$\pi$
$\pi$

$\pi$ будет повторяться с 1 или 0 . Точно так же вы не можете перестать находить 11 или 00 , потому что в противном случае они начинают повторяться на 1010101 ...
5. Индуктивный шаг: каждая конечная последовательность должна появляться бесконечное число раз, потому что альтернативой является то, что начинает повторяться на одна из более коротких последовательностей, что противоречит R .$\pi$