Теория алгоритмов.

[maxmatem]

добрый вечер! задание состоит в том что надо доказать что функция $f(x)=x!$ примитивно рекурсивная. я начал строить примитивно рекурсивное описание $f(x)=x!$.
сначала я рассмотрел естественное описание данной функции т.е.
$f(0)=0!=1$
$f(y+1)=(y+1)!$.

теперь применяю определение операции примитивной рекурсии к ф-ии $f(x)=x!$
$f(0)=g(x)$
$f(y+1)=h(y;f(y))$

теперь осталось найти $g(x)$ и $h(x;y)$
ну то, что $g(x)=C_{1}=1$.
а вот с $h(x;y)$ возникают проблемы........ я попробывал $h(x;y)=S(s;I_{2}(y;f(y)))$ но не вышло.
$S$-оператор подстановки
$s$-оператор следования

[Xaositect]

Сначала нужно умножение.
$h(y,f(y)) = (y+1)\cdot f(y)$
Через свои обозначения сами пишите.

[maxmatem]

вот кажется получилось ! проверьте!
$f(0)=1$
$f(x+1)=(x+1)!=(x+1)x!$
это естественное задание ф-ии

$f(0)=g(x)$
$f(x+1)=h(x;f(x))$
это применил определение примит.рекурсии.
тогда:
$g(x)=C_{1}=1$
$h(x;y)=S(*;S(s;I_{1}(x;y));I_{2}(x;y))$
теперь докажем что $f=R(g;h)$
$f(0)=g(x)=C_{1}=1$
$f(x+1)=h(x;f(x))=S(*;S(s;I_{1}(x;f(x)));I_{2}(x;f(x)))=S(*;S(s;x);f(x))=S(*;s(x);f(x))=s(x)*f(x)=(x+1)*x!=(x+1)!$
где $*$-это умножение
где $S$-операция подстановки
где $s$-операция следования
Проверьте пожалуйста!

[Xaositect]

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

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

Все верно.

[maxmatem]

спасибо,что проверили!