Пусть 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.

Правильный ответ:

• # [Большая Картинка] Какую булеву функцию реализует эта логическая схема в вершине a ?
• # [Большая Картинка] Какую булеву функцию реализует эта диаграмма? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)
• # Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∧ x2) +( x3 ∧ x4) относительно двух упорядочений переменных: a) x1 < x2 < x3 < x4 иb) x1 < x3 < x2 < x4. Определите сложности этих двух схем.
• # Какие из следующих трех конечных автоматов Ai = < {a,b}, {0, 1, 2, 3}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на a и содержат четное число букв b ? [Большая Картинка]
• # Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на abb и содержат число символов b кратное 3, и пусть гоморфизм h: {0, 1,2}* →​ {a, b}* задан равенствами: h(0) = bab, h(1) = b, h(2) = ε Какие из следующих трех слов принадлежат прообразу h-1(L) языка L при гомоморфизме h? W1 = 210102012, W2 = 201000201021, W3 = 021010212