Примитивно рекурсивные функции

[Rocky095]

Доброго времени суток, уважаемые форумчане!
Задача:
Доказать, что предикат NU(x) является (или не является) (примитивно) рекурсивным, где NU(x):
"Х есть Гёделев номер цифры".

Вот до чего я додумался:
Пусть дан предикат $NU(x)$, где $x=2^{15}$-гёделев номер цифры,
тогда выражая предикат $NU(y) \& x=2^{57} 2^3 y 2^5$ через отношение $H(x_1,...x_n,y)$,
а предикат NU(x) через $R(x_1,...x_n,x)$, то так как значение функции для произвольного X определяется через его значение для аргументов меньших, чем $x (x<y)$ , то учитывая тот факт , что
$x=2^{15}\bigvee\exists y_{y<x}(NU(y)\& x=2^{57} 2^3 y 2^5)$
получим, что $R(x_1,..x_n,x)$ эквивалентно $C_R(x_1,..x_n,x)=0$, так как $y<x$, то
$(C_R)_\sharp (x_1,..x_n,x)y=0$;
$C_R(x_1,..x_n,x)=C_H(x_1,..x_n,y,(C_R)_\sharp(x_1,..x_n,x))$
Следовательно:
$R(x_1,..x_n,x)=H(x_1,..x_n,y(C_R)(x_1,x_n,x))$ , (где $C_R$-характеристическая функция отношения R), следовательно и отношение $R=NU(x)$ - примитивно рекурсивно.

Препод сказал, что это слишком обще и нужно больше конкретизировать..как то от характеристической функции $\exists y_{y<x}(NU(y))$ отталкиваться и показать что предикат будет выражаться как бы сам через себя..как это сделать не догадываюсь..есть у кого каие мысли по этому вопросу?
Заранее спасибо)

[Toucan]

Тема перемещена в Карантин.

Запишите формулы (включая собственные попытки решения) в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.

[AKM]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

[Профессор Снэйп]

Это что за гёделевы номера у цифр? Никогда о таком не слышал.

[Rocky095]

Профессор Снэйп в сообщении #583314 писал(а):

Это что за гёделевы номера у цифр? Никогда о таком не слышал.

Вот что написано в Мендельсоне:
цифры,стр.121:
Термы 0,0',0'',0''',... мы в дальнейшем будем называть цифрами и обозначать, как обычно, $\overline{0},\overline{1},\overline{2},\overline{3},...$ И вообще, для любого целого неотрицательного $n$ соответствующую цифру 0'''...', т.е. 0 с $n$ штрихами, будем обозначать через $\overline{n}$. Цифры можно определить рекурсивно: 0 есть цифра; если u-цифра, то и $\overline{u}$- цифра.
Гёделевы номера, стр151:
Каждому символу u произвольной теории первого порядка К следующим образом поставим в соответствие положительное число g(u), называемое гёделевым номером символа u:
$g(()=3; g())=5; g(,)=7; g(\neg)=9;...$
Таким образом, различным символам поставлены в соответствие различные гёделевы номера, являющиеся положительными нечётными числами.

На странице 157
Предложение 3.27 Примитивно рекурсивными являются и следующие отношения:
(14) (а) Nu(y) : "y есть гёделев номер некотрой цифры теории S"
$y=2^{15} \bigvee \exists x_{x<y}(NU(x) \& y=2^{57} 2^3 x 2^5)$. Применить следствие 3.20 на странице 146

[Rocky095]

как то так

[Toucan]

Rocky095, замечание за искусственный подъем темы.