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

[Sverest]

У меня такое задание:
Доказать примитивную рекурсивность функции

$f(x)=|x-y|$

это не опечатка случайно? может надо $f(x,y)=|x-y|$ ?

[Sonic86]

Sverest в сообщении #552990 писал(а):

$f(x)=|x-y|$

это не опечатка случайно? может надо $f(x,y)=|x-y|$ ?

Конечно опечатка.

Sverest в сообщении #552990 писал(а):

У меня такое задание:
Доказать примитивную рекурсивность функции

$f(x,y)=|x-y|$

выразите $f$ через усеченную разность.

[Sverest]

$|x-y|=(x \dot{-} y)+(y \dot{-} x)$

-- Ср мар 28, 2012 17:22:26 --

$f(x,0)=(x \dot{-} 0)+(0 \dot{-} x)\\ f(x,0)=x$

$f(x,y+1)=(x \dot{-} y+1)+(y+1 \dot{-} x)$

я правильно сделал?

[Sonic86]

Угу, даже 2-я способами Причем это

Sverest в сообщении #553051 писал(а):

$f(x,0)=(x \dot{-} 0)+(0 \dot{-} x)$

не нужно

[Sverest]

как это двумя?
почему не нужно?
я посмотрел вроде чтоб доказать надо представить в виде:

$h(x_1,\ldots,x_n,0)=f(x_1,\ldots,x_n)$
$h(x_1,\ldots,x_n,y+1)=g(x_1,\ldots,x_n,y,h(x_1,\ldots, x_n,y))$

мне кажется чего то не хватает

[Sonic86]

2 способа:
1. Через некоторые простые леммы о ПРФ и знании некоторых конкретных функций, которые являются ПРФ.
2. По определению ПРФ.
Вы сделали обоими, если вдуматься.

[Sverest]

меня вот эта формула интересует:
$h(x_1,\ldots,x_n,y+1)=g(x_1,\ldots,x_n,y,h(x_1,\ldots, x_n,y))$

где у меня здесь $h(x_1,\ldots, x_n,y)$?

в $f(x,y+1)=(x \dot{-} y+1)+(y+1 \dot{-} x)$

[_hum_]

Sverest
Докажите, что примитивно рекурсивными являются функции:
1) $h_{{}_{\dot{-}}}(u, v) = u\, \dot{-}\, v $
2) $h_{{}_+}(u, v) = u + v $.
Затем попытайтесь выразить вашу функцию в виде композиции этих двух. Если это удастся сделать, то тем самым удастся доказать, что она тоже примитивно рекурсивная (почему?).