Пусть функция F(x) задана примитивной рекурсией R(1, h(y,z)), где h(y,z) = [2z/z2]Чему равно значение F(5)?

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

• # [Большая Картинка] Какую булеву функцию реализует эта логическая схема в вершине a?
• # Следующий конечный автомат - преобразователь MINUS= <ΣX ={0, 1} ΣY= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?
• # Какой язык L является конкатенацией двух языков: L1= {a, ab, abba} и L2= { ε, a, b, ba}?
• # Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {S}, ΦA > с программой ΦA: { Q a →​ R, Q b →​ P, P b →​ P, P a →​ R, R a →​ Q, R b →​ S, S a →​ R, S b →​ S} и гомоморфизм h: {0, 1, 2}* →​ {a, b}*: h(0) = bab, h(1) = aba, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)? С1 = < {0, 1}, { Q, P, R, S }, 0, F1={S}, Φ1>, С2 = < {0, 1}, { Q, R, S }, 0, F2={ S }, Φ2>, С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ S }, Φ3>, где программы заданы в следующих таблицах. [Большая Картинка]
• # Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1, с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст ); if Больше12 then par#( Пуст, Сум ) else par#( Пуст, Умн ) endif; Зам(#, *); Выб33. Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 3, x2 = 6 и при x1 = 2, x2 = 6, соответственно?