Проверить примитивную рекурсивность функции

[irino4ka]

помогите очень срочно нужно доказать что функция примитивно рекурсивна или нет .. функция f(x) система, если число делится на 5 то f(x)=1 иначе равна нулю . помогите пож с простенькой задачкой .. заранее спасибо ..

[Андрей АK]

Любая функция примитивнорекурсивна ... если можно записать алгоритм её вычисления через дурацкие прибавления единицы,рекурсию и выбор по номеру из списка.
Значит в задаче требуются просто построить такой алгоритм (не представляю как можно доказать, что такого алгоритма построить невозможно?) и этим все и доказать.

По моему, вот так будет выглядить проверка деления на 5:

F(X) = 1 ; X=0
F(X) = 0 ; X=1
F(X) = 0 ; X=2
F(X) = 0 ; X=3
F(X) = 0 ; X=4
F(X) = N(X,5) ; X>4
N(X,M) = F(M) ; X=0
N(X,M) = N(X,5) ; X>0 ,M=0
N(X+1,M+1) = N(X,M) ; X>0 ,M>0

Запрещённых операций нет? Значит доказано.
PS
Ах да наверное ж надо ещё как-то представить условие типа X=4 или M>0 через функцию выбора из списка аргументов или не надо?
Чесно говоря я таких тонкостях не очень разбираюсь ... вот какой-то алгоритм написал ... и ладно.

[irino4ka]

спасибо большое но дело в том что именно алгоритм и написание программы вот в чем была цель работы а в конце надо было доказать рекурсивность ну ясно что она рекурсивно но как то формально это нужно было написать вот именно что требовалось .. в этом помоч бы ..

[Maslov]

irino4ka в сообщении #270408 писал(а):

помогите очень срочно нужно доказать что функция примитивно рекурсивна или нет .. функция f(x) система, если число делится на 5 то f(x)=1 иначе равна нулю .

Посмотрите в задачнике Игошина (Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов) пример 13.6 б): там доказывается примитивно-рекурсивность функции $r(x,y)$ (остаток от деления $y$ на $x$). Ну а от $r(5, x)$ до Вашей - уже рукой подать.

[PAV]

Учебная задача отделена в соответствующий раздел

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

Андрей АK в сообщении #270460 писал(а):

По моему, вот так будет выглядить проверка деления на 5:

F(X) = 1 ; X=0
F(X) = 0 ; X=1
F(X) = 0 ; X=2
F(X) = 0 ; X=3
F(X) = 0 ; X=4
F(X) = N(X,5) ; X>4
N(X,M) = F(M) ; X=0
N(X,M) = N(X,5) ; X>0 ,M=0
N(X+1,M+1) = N(X,M) ; X>0 ,M>0

Запрещённых операций нет?

Формально это не схема примитивной рекурсии. Если теорему о соответствующем типе рекурсии доказывали, то всё Ok, иначе нет.

[alexlacky]

Приветствую.... ребята, помогите....
Показать примитивную рекурсивность функции f(x,y)

$$ f(x,y)=\begin{cases} 3, & 2\le y \le 6\\ x+1,&\text{иначе;} \end{cases} $$

[PAV]

Вы должны написать свои попытки, соображения и затруднения. А еще было бы очень неплохо прочитать правила этого раздела, которые написаны вверху страницы на специально выделяющемся желтом фоне