Функция ищет подпоследовательности цифр

11

Как можно решить, имеет ли некоторую последовательность цифр? πвдохновил меня на вопрос, можно ли вычислить следующую невинную версию:

f(n)={1if n¯ occurs in the decimal representation of π0otherwise

где - десятичное представление n без начальных нулей.n¯n

Если десятичное разложение содержит все последовательности конечных цифр (назовем это универсальным числом (в базе 10)), то f является константой 1 . Но это открытый математический вопрос. Если π не универсален, означает ли это, что f невычислимо?πf1πе

Жиль "ТАК - прекрати быть злым"
источник
уловка для другой проблемы работает, потому что это унарно, этот трюк не будет работать для проверки двоичных строк. Но это не значит, что по-другому это невозможно.
Каве
@Kaveh Что вы подразумеваете под "унарный"? Связанный вопрос рассматривал десятичное представление . π
Рафаэль
Это один из способов сделать пример невычислимым. Другой способ - ввести действительное число в качестве входных данных. У меня нет под рукой доказательств. π
Рафаэль
1
@Kaveh: Мы могли бы также проверить наличие без изменения ответа. (01)N
Рафаэль
1
@ Рафаэль, ты можешь думать об этом, как об одном и том же. (Важная вещь - это структура возможных строк для проверки отношения префикса.)
Kaveh

Ответы:

3

Обратите внимание, что может быть константой 1, даже если π не является нормальным числом. (По-французски мы говорим, что если f константа, то π - универсальный номер . Я не знаю соответствующего термина в английском)е1πеπ

Для чего это стоит: это может быть , следующим образом:

Доказательство того, что вычислимо, не обязательно подразумевает решение открытого вопроса, является ли f постоянным или нет. Например, вы можете построить g, который вычислим, но такой, что постоянство g эквивалентно гипотезе Гольдбаха .ееграммграмм

Конечно, это даже не начинает отвечать на ваш вопрос, но, скорее всего, он открыт для меня.

jmad
источник
Да , на самом деле я имел в виду более универсальный . Таким образом, может быть вычисляемым, не будучи постоянным. Я уверен, что есть простой способ показать это. Не могли бы вы объяснить немного больше, как f может быть или не быть вычислимой на уровне теории вычислимости 101? ее
Жиль "ТАК - перестань быть злым"
Ну, я хотел ответить на вопрос «Учитывая, что - сложный вопрос ] , означает ли f 1, что P ( f ) ?» и мой ответ : «Почему нет? По крайней мере , ¬[е?знак равно1]е1п(е) не означаетчто [ е ? = 1 тривиальный вопрос ] »¬п(е)[е?знак равно1]
jmad