Чему равна глубина схемы S₃, реализующей функцию сложения трехбитовых чисел?

Чему равна глубина схемы S₁, реализующей функцию сложения однобитовых чисел?

Чему равна глубина схемы S_odd , реализующей функцию odd(X₁, X₂, …,X_n) = X₁ + X₂ + … X_n ?

Пусть задана линейная программа 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.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = ¬X1;

Z = ¬X2;

U = ¬X3;

Y = Y ∧ X2;

W = X2 ∧ X3;

Y = Y ∧ U;

Y = W ∨ Y ;

Z = Z ∨ Y.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = X1 ∨ X2;

Z = X1 ∨ X3;

U = ¬X3;

Y = Y ∧ Z;

W = X2 ∨ X3;

U = X2 ∨ U;

Z = W ∨ Y ;

Z = U ∧ Y.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x* |^y в конфигурацию |^y * |^x* ∧ *|^g(x) , используя м.Т. M_g, вычисляющую функцию g(x).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?

P1 = Коп_# ; par_# (par_* (Чист, Пуст); Зам(*,∧ ) , par_* (Пуст ,Чист); Зам(*,∧ ) ); par_# (Пуст, Коп_* ); par_* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par_* (Пуст, Пуст, M_g); Зам( #,* )

P2 = Коп_# ; par_# (par_* (Чист, Пуст); Зам(*,∧ ) , par_* (Пуст ,Чист); Зам(*,∧ ) ); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )

P3 = Коп_* ; par_* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a – копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂ ( a ∉ w₁ );

Пуст – не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

+1 – прибавляет 1 к аргументу: |^x ⇐ |^x+1

В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g², f⁴), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x1*|^x2* |^y в конфигурацию |^y * |^x1*|^x2* ∧ *|^g(x) , используя м.Т. M_g, вычисляющую функцию g(x1,x2).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?

P1 = Коп_# ; par_# (par_* (Чист, Чист,Пуст); Зам(*,∧ ) , par_* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par_# (Пуст, Коп_* ); par_* (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* ))

P2 = Коп_# ; par_# (par_* (Чист, Чист , Пуст); Зам(*,∧ ) ; Зам(*,∧ ), par_* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )

P3 = Коп_* ; par_* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂ ( a ∉ w₁ );

Пуст - не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

+1 - прибавляет 1 к аргументу: |^x⇐ |^x+1

В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₂, которая переводит конфигурацию вида |^y *|^x* |^u* |^z в конфигурацию |^y *|^x* |^u+1* |^f(x,u,z) , используя м.Т. M_f, вычисляющую функцию f(x,u,z).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₂ ?

P1 = Зам(*,# ); par_# ( Пуст, Коп_#); par_# (Пуст, Пуст, M_f ); Зам( #,* ); Зам( #,* )

P2 = Зам(*,# ); par_# ( Пуст, Коп_#); par_# (Пуст, Пуст, M_f ); par_# (Пуст, par_* (Пуст, +1, Чист), Пуст); Зам( #,* ); Зам(∧, |); Зам( #,| ); par_* (Пуст, Пуст, Пуст, Выч1; Выч1)

P3 = Зам(*,# ); par_# ( Пуст, Коп_#); par_# (Пуст, par_* (Пуст, +1, Чист), M_f ); par_* (Зам( #,* ), Пуст, Зам(∧, |); Зам( #,| ); Выч1; Выч1)

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂ ( a ∉ w₁ );

Пуст - не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

Выч1 – вычитает единицу в унарной системе: |^j ⇐ |^j-1 (| ⇐ ∧, ∧ ⇐ ∧);

+1 - прибавляет 1 к аргументу: |^x⇐ |^x+1

Пороговая функция T_n,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T_5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

Пороговая функция T_n,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T_5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?