Пусть c2(x, y) = 2x(2y+1) -1 - это функция - Ответ на вопрос по любому предмету №1171047

Вопрос

Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами:F(0) = 0, F(1) = 1, F(y+2) = F(y) + F(y+1) +1. Положим G(y) = c2(F(y), F(y+1)). Так какF(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.

• R( 1, [c2; [c22; I22], [+; [c21; I21], [c22; I22]])
• R( 2, [c2; [c22; I22], [s; [+; [c21; I22], [c22; I22]]])
• R( 2, [c2; [c21; I22], [+; [c21; I22], [s;[c22; I22]]])
• R( 1, [c2; [c22; I22], [+; [c21; I22], [s; [c22; I22]]])
• ни одна из выше перечисленных

Ответ