Примитивно рекурсивный предикат

[maxmatem]

надо доказать, что предикат $Pr(x)$-"x-простое число" является примитивно рекурсивный предикат.проблема состоит в том что, я пока не могу записать этот предикат в явном виде!

[Maslov]

Можно, например, здесь посмотреть: Петер Р. — Рекурсивные функции.

[maxmatem]

Я вот так придумал ! рассмотрим функцию

$$d(x)=\sum\limits_{i=1}^x Div(x;i)$$

где $d(x)$ это функция считающая число различных делителей числа $x$, не превосходящих числа $x$. тогда надо подобрать представляющею функцию $q(x)$ когда $Pr(x)=$И то $q(x)=0$,
и когда $Pr(x)=$Л то $q(x)=0$.
тогда на роль такой функции подходит $q(x)=sg|d(x)-2|$ и она ПРФ. значит по определению предикат $Pr(x)$ -ПРП.
проверьте , пожалуйста!!

Кстати, Maslov! с той ссылки что вы дали книгу скачать нельзя!

[Xaositect]

maxmatem в сообщении #296809 писал(а):

проверьте , пожалуйста!!

Пара опечаток, но в общем все верно.

maxmatem в сообщении #296809 писал(а):

Кстати, Maslov! с той ссылки что вы дали книгу скачать нельзя!

free-books.dontexist.com

[maxmatem]

спасибо!