Доказать что функция F(x,y)=2x+y+7 частично рекурсивна

[n45]

Здравствуйте. Помогите доказать что функция $F(x,y)=2x+y+7$ частично рекурсивна. Заранее благодарю.

[Xaositect]

Она является композицией частично-рекурсивных функций --- сложения, умножения и константы

[n45]

а, можно чуть-чуть поподробнее, пожалуйста...

[Xaositect]

n45 в сообщении #221806 писал(а):

а, можно чуть-чуть поподробнее, пожалуйста...

Дайте определение частично-рекурсивной функции

[n45]

Функция f называется частично рекурсивной функцией (ч.р.ф.), если она является одной из простейших функций или может получиться из них с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации, т.е. существует последовательность функций f1,f2,…, fn=f, каждая из которых является либо простейшей, либо получена из предыдуших с помощью одного из указанных операторов. Указанная последовательность функций называется частично рекурсивным описанием функции f.

[Xaositect]

Хорошо.
Как я уже сказал, наша функция может быть получена композицией из сложения, умножения, константы 2 и константы 7. Это понятно?

Осталось получить эти функции из простейших с помощью композиции и рекурсии. С константами понятно? Нейжели в учебнике или в лекциях не было в качестве примера утверждения о том, что сложение рекурсивно? Если нет, то вот этот пример, который можно найти в любой книжке по данной области.
$x+0 = x$
$x+(y+1) = s(x+y)$ ($s$ - это функция, прибавляющая к числу единицу)
Понятно ли, что это есть применение оператора рекурсии?

С умножением попробуйте разобраться сами.

[n45]

Спасибо большое. вполне доступно. с остальным сам разберусь.