Теория алгоритмов, А тут мне помогут?:( Опции

[TOPEHTO]

Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?

[Michael_Rybak]

НОД: покажи, что min и max примитивно-рекурсивны, и юзай формулу НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))

НОК: покажи, что умножение и деление примитивно-рекурсивны, и юзай формулу НОК(x, y) = x * y / НОД(x, y)

[Fanat]

Умножение вот так:
M(2)(X,0)=g(X)=0.
M(2)(X,A+1)=h(X,A,M(X,A))=x*a+a=A(M(X,A),X)

M=ро(оперотор примитивной рекурсии)[N(1),Сигма[A,I(3,3),I(3,1)]]

Использовали x(a+1)=x*a+x

Запись M(2)-арность функции M-2.
Запись I(3,1)-арность 3,выбирает первый элемент.

Где А-сложение описываетьсята так-

A(2)(X,0)=g(X)=X=I(1,1)
A(2)(X,A+1)=h(X,A,A(X,A))=S(A(X,A))=сигма[S,I(3,3)]

x+(a+1)=(x+a)+1.

Вроде так всё.Сигма-оператор суперпозиции.