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

130

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

Позволять

f(n)={10n occurs in the decimal representation of π0else

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

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

Рафаэль
источник
32
Прости меня за то, что я совершенно невежественен, я, очевидно, упускаю какой-то фундаментальный вопрос, но разве 0 ^ n не всегда 0? Поскольку 32-й знак после запятой, если pi равен 0, разве это не означает, что f (n) всегда возвращает 1?
Кори Кляйн
69
@CoryKlein: это формальная нотация языка ; верхний индекс здесь означает - кратную конкатенации, т.е. . здесь только символ, а не число. nna5=aaaaa0
Рафаэль

Ответы:

133

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

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

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

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

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


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

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

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

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

sepp2k добавляет:

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

JeffE
источник
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .
Жиль
12
Что произойдет, если кто-то докажет, что утверждение «Для каждого натурального числа n строка 0 ^ n появляется в десятичном представлении π» недоказуемо? Будем ли мы все еще говорить, что эта проблема разрешима, несмотря на то, что невозможно построить правильный алгоритм?
другие
4
@ Другое Да, мы бы.
Джефф
1
@ Джефф Хорошо. Возможно ли доказательство в интуиционистской логике? Или здесь нужен закон исключенного среднего?
другие
@ Прочие Если я правильно понял, идея такова: если мы для каждого определяем машину Тьюринга как в первой части ответа, то мы знаем, что один из них вычисляет эту функцию. Мы не знаем, какой из них (и если бы ваше утверждение было доказано, мы бы даже знали, что невозможно знать, какой именно), но мы все еще знаем, что существует такая машина Тьюринга , поэтому функция является вычислимой. NMN
JiK
14

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

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

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

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

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

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

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

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

JC
источник
9
Не все математики принимают это, например, интуиционисты.
reinierpost 10.07.13
Вы в основном делаете длинный пример закона исключенного среднего, , lol. В интуиционистской логике или любой логической системе, основанной на теории типов, это доказательство отклоняется. P¬P
Kaa1el
5

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


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

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

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

Стивен Ворис
источник
10
Прежде всего, мы знаем, что двоичное расширение не повторяется, поскольку иррационально. Во-вторых, существуют иррациональные числа, которые не содержат ни 000, ни 111 в двоичном разложении, например, число, соответствующее последовательности Туэ-Морса: 0.0110100110010110 ...ππ
Yuval Filmus
1
Ах, опасность индуктивных скачков: P Хороший улов, спасибо.
Стивен Ворис
1
Кстати, если заключение неверное, имеет ли смысл для меня удалить его или оставить его и подтвердить через редактирование, что оно неверное?
Стивен Ворис
4
@StephenVoris Это зависит от того, насколько образовательным вы считаете ошибку. Отметим, что вопрос о том, является ли нормальным (т. Е. Его разложение по основанию содержит каждую конечную последовательность -арных цифр бесконечно часто), является одной из больших открытых проблем теории чисел. πbb
Дэвид Ричерби
2
@DavidRicherby Большая открытая проблема, говорите? Да, это приятно знать. Я действительно считаю, что это разумная образовательная ошибка, поскольку доказательство того, насколько сложна проблема, на которой основан вопрос ОП, - очевидно, я тоже могу ошибаться, учитывая отрицательное мнение.
Стивен Ворис