Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функц
Пусть 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) = 1, F(1) = 1, F(y+2) = F(y) + F(y+1) . Положим G(y) = c2(F(y), F(y+1))Так как
F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность GОпределите, какая из следующих примитивных рекурсий задает G
вопрос
Правильный ответ:
R( 5, [c2; [c21; I22], [+; [c21; I22], [c22; I22]])
R( 1, [c2; [c22; I22], [+; [c21; I21], [c22; I22]])
R( 2, [c2; [c22; I22], [+; [c21; I21], [c22; I22]])
R( 5, [c2; [c22; I22], [+; [c21; I22], [c22; I22]])
ни одна из выше перечисленных
Сложность вопроса
35
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень простецкий вопрос интуит.
18 авг 2018
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Следующий конечный автомат - преобразователь MINUS= <ΣX ={0, 1} ΣY= { 0, 1}, Q ={ 0, 1, 2 }, 0, Φ, Ψ>, где [Большая Картинка] вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?
- # Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию S* этого языка?
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= 1; если x < z то y := z иначе y:=x конецP2: x := y+1; z:= x +1; если x < z то y := z иначе y:=x конецP3: x := y+1; z:= x +1; пока u < z делай y := z; u := u+1 все
- # Пусть структурированная программа P: x:= y+1; z := x+1; x := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии σ : σ(x) =3, σ(y) =5, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?
- # Пусть заданы три функции: f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2 Какую функцию F(x1,x2) задает выражение [f;[g;I21, I21], I21 , [h; I22 ]] ?