Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть 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) = 2, 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( 9, [c2; [c21; I22], [×; [c21; I22], [c22; I22]])
R( 9, [c2; [c22; I22], [×; [c21; I22], [c22; I22]])
R( 2, [c2; [c22; I22], [×; [c21; I21], [c22; I22]])
R( 2, [c2; [c22; I22], [×; [c21; I21], [c22; I22]])
ни одна из выше перечисленных
Сложность вопроса
26
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Если бы не опубликованные ответы - я бы не решил c этими тестами интуит.
11 янв 2020
Аноним
Большое спасибо за ответы по интуиту.
08 янв 2018
Аноним
Если бы не опубликованные ответы - я бы не смог решить c этими тестами intuit.
10 фев 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана линейная программа P со входными переменными X1, X2, X3: Y = ¬X1;Z = ¬X2;U = ¬X3;V = X1 ∧ X2;Z = Y ∧ Z;W= Y ∧ X2;Z = Z ∧ W ;V = V ∧ U ;Z = Z ∨ V. Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?
- # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?
- # Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере две подряд идущие 1-цы ?
- # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +2 ? [Большая Картинка]
- # Пусть функция F(x) задана примитивной рекурсией R(1, h(y,z)), где h(y,z) = [2z+1/z]Чему равно значение F(3)?