Выразимы ли наилучшие корни?

[knizhnik]

Рассмотрим функцию $f$, которая для каждого натурального аргумента $n$ принимает значение $n+1$-значного натурального числа $f(n)$, квадрат которого наиболее приближен к числу $2 \cdot 10^{2n}$:
$\forall m,n \ (m^2 < 2 \cdot 10^{2n} \Rightarrow m^2 \leq f(n)^2 < 2 \cdot 10^{2n})$
Для вашего удобства понимания условия можно вычислить несколько первых значений:
$f(0)=1 \ \wedge \ 1^2 = 1 \approx 2$
$f(1)=14 \ \wedge \ 14^2 = 196 \approx 200$
$f(2)=141 \ \wedge \ 141^2 = 19881 \approx 20000$
$f(3)=1414 \ \wedge \ 1414^2 = 1999396 \approx 2000000$
Построим множество наилучших корней: $\{g \ | \ \exists n \ g=f(n) \}=\{1,14,141,1414, \ldots \} $. Выразима ли принадлежность этому множеству в арифметическом языке?

[mihaild]

Придумать алгоритм, проверяющий принадлежность этому множеству, вы можете? (не обязательно эффективный - вполне допустимо перебирать все числа данной разрядности)

[knizhnik]

mihaild, я не знаю, что такое алгоритм, тем более эффективный. Но как бы я проверил вручную. Возьмем некоторое $x$ и возведем его в квадрат. Если $x^2$ - число $2n+1$-значное (нечетнозначное), то убеждаемся, что $x^2<2\cdot 10^{2n}$ и проверяем дальше все неравенства $(x+1)^2<2\cdot 10^{2n},(x+2)^2<2\cdot 10^{2n},(x+3)^2<2\cdot 10^{2n}, \ldots $ до тех пор, пока какой-то квадрат суммы перестанет быть меньше требуемого значения. Если хоть одно из неравенств оказалось верным, то $x$ не является наилучшим корнем. Если $x^2$ - число $2n$-значное, то все делается так же. Если внезапно $x^2 \geq 2\cdot 10^{2n}$, то $x^2 < 2\cdot 10^{2n+2}$, и снова выполняется такой же перебор.

Но у меня вопрос не о том, как выполнить перебор, а о формальной выразимости предиката в арифметике.

[mihaild]

Есть тезис Чёрча о том, что для всех подобных описаний можно составить машину Тьюринга, их проверяющую (т.е. если вы можете описать процедуру проверки, то можно построить МТ, ее проводящую). И есть теорема о том, что всякое множество, принадлежность которому проверяется некоторой МТ, выразимо $\Sigma_1$ формулой.
Если хочется напрямую - то из интересного тут выразимость предиката "число $k$ имеет $n$ десятичных разрядов". Выражается примерно как "существует число, кодирующее последовательность из $n$ чисел, из которых первое - $1$, последнее - $k$, и каждое следующее равно предыдущему, умноженному на $10$".
Экспонента (двоичная) у вас в языке есть?

[knizhnik]

mihaild в сообщении #1195810 писал(а):

Есть тезис Чёрча о том, что для всех подобных описаний можно составить машину Тьюринга, их проверяющую (т.е. если вы можете описать процедуру проверки, то можно построить МТ, ее проводящую). И есть теорема о том, что всякое множество, принадлежность которому проверяется некоторой МТ, выразимо $\Sigma_1$ формулой.

Какой формулой? Объясните подробнее.
Если что, выразимость прямо зависит от используемого языка, аксиом, смысла предикатов и операций. Ну, вот $P(x) = (\exists n \ x=n!)$ никак не выражается через сложение, равенство и умножение. Но для свойства $P(x)$ числа быть факториалом можно осуществить такого же плана проверку: разделим $x$ сначала на $2$, затем (если повезло) на $3$ ...

mihaild в сообщении #1195810 писал(а):

Экспонента (двоичная) у вас в языке есть?

В арифметике Пеано? Откуда?

[Anton_Peplov]

knizhnik в сообщении #1195798 писал(а):

я не знаю, что такое алгоритм

Это машина Тьюринга. Или машина с неограниченными регистрами. Или алгоритм (в оригинальной орфографии алгорифм) Маркова. Все эти определения алгоритма эквиваленты в том смысле, что приводят к одному и тому же классу вычислимых функций (совпадающему, кстати говоря, с классом всех частично-рекурсивных функций). Эти сведения можно почерпнуть из любого начального курса теории алгоритмов. Ну а далее

mihaild в сообщении #1195810 писал(а):

теорема о том, что всякое множество, принадлежность которому проверяется некоторой МТ, выразимо $\Sigma_1$ формулой.

knizhnik в сообщении #1195831 писал(а):

Ну, вот $P(x) = (\exists n \ x=n!)$ никак не выражается через сложение, равенство и умножение.

В арифметике Пеано это предикат выразим. Согласно процитированной теореме.

[knizhnik]

Anton_Peplov в сообщении #1195835 писал(а):

В арифметике Пеано это предикат выразим.

Придется спросить у вас, а как непосредственно выразить этот предикат?

Anton_Peplov в сообщении #1195835 писал(а):

Согласно процитированной теореме.

Укажите первоисточник, тогда, возможно, через некоторое время я смогу разобраться, что такое $\Sigma_1$ формула.

[Anton_Peplov]

knizhnik в сообщении #1195843 писал(а):

Придется спросить у вас, а как непосредственно выразить этот предикат?

Не знаю. Мне этого не надо знать так же, как не надо уметь программировать на ассемблере. Я не любитель тренироваться в закате Солнца вручную (хотя не спорю, что в этом занятии при желании можно найти и пользу, и прелесть).

knizhnik в сообщении #1195843 писал(а):

Укажите первоисточник

Попробуйте Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Я не уверен, что там используется именно термин "$\Sigma_1$-формула", но арифметичность графика любой вычислимой функции там доказывается (а это именно то, что нужно для ответа на Ваш первоначальный вопрос и на все ему подобные).

[Xaositect]

В Мендельсоне ("Введение в математическую логику", глава 3) есть. Кратко тут: https://en.wikipedia.org/wiki/Primitive ... arithmetic