В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M43 ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})P1: q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П ,P2: : q <a, b, c, | > → q < a, b , c, | > П , s < a , b, |, d > → s < a , b, |, | > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q <a, b, ∧, ∧> → s < a , b, ∧, ∧ > Л , s < a , b, ∧, | > → s < a , b, ∧, ∧ > Л,P3: : q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q <a, b, ∧, | > → q < a, b, ∧, ∧ > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,
В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M31, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M31 ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})P1: q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q <∧, b, |, d > → q < ∧, b, ∧, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,P2: : q <|, b, c, d > → q < |, b , c, d > П , s < ∧ , b, |, d > → s < | , b, ∧, d > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < | , b, c, d > → s < | , b, |, d > Л ,P3: : q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П.
В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее
CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида
x * q y (
x и
y – слова в алфавите
Σ, не содержащем символов
∧,
* и
# ,
q – начальное состояние) в конфигурацию
y* q’ x (
q' – заключительное состояние). Пусть
Q={ q, s, p, r, q'}∪ {pa | a ∈ Σ} – множество состояний
CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для
CHANGE ?(В текстах программ a – это произвольный символ из
Σ, а b - это произвольный символ из
Σ ∪ {*, #} ).
P1: q b → q b П , q ∧ → s # Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r # → q’ * П.
P2: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r*→ q’ * П.
P3: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → q’ * П, pa b → pa b П, pa ∧ → s a Л.
В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее
MOVE, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее,
MOVE, начав работать в конфигурации вида
q a w1 #k#' (
a ∈Σ, w1 ∈Σ*, k ≥ 0), должна завершить работу в конфигурации
∧kpa'w1 Пусть алфавит ленты
MOVE включает символы из
Σ ∪ {a' | a ∈ Σ}∪ {∧, #, #'}, а алфавит состояний
Q= {q, p, r} ∪ {pa | a ∈ Σ}Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для
MOVE ?(В текстах программ
a и
b – это произвольные символы из
Σ),
P1: q a → pa ∧ П , q a' → p a' Н , pa b → pb a П, pa b' → pb a' П, pa # → r a Л, pa #' → r a' Л, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.
P2: q a → pa ∧ П , pa b → pb a П, pa b' → pb a' П, pa # → r a Л, pa #' → r a' Л, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.
P3: q a → pa ∧ П , pa b → pa b П, pa # → pa # П, pa #' → r a Л, pa b' → pa b' П, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П, q # → q ∧ П , q a' → p a' Н.
Пусть задана линейная программа 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. Чему равна ее глубина?
Пусть задана линейная программа 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.
Постройте логическую схему SP со входами 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.
Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?
В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* ) P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* ) P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )
В этих определениях участвуют следующие простые машины Тьюринга:Копa – копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст – не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;+1 – прибавляет 1 к аргументу: |x ⇐ |x+1
В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии
F(x1,x2, y) = R( g2, f4), требовалась м.Т.
M1, которая переводит конфигурацию вида
|x1*|x2* |y в конфигурацию
|y * |x1*|x2* ∧ *|g(x) , используя м.Т.
Mg, вычисляющую функцию
g(x1,x2).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для
M1 ?
P1 = Коп# ; par# (par* (Чист, Чист,Пуст); Зам(*,∧ ) , par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп* ); par* (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* ))P2 = Коп# ; par# (par* (Чист, Чист , Пуст); Зам(*,∧ ) ; Зам(*,∧ ), par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )P3 = Коп* ; par* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )
В этих определениях участвуют следующие простые машины Тьюринга:
Копa –копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст - не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;+1 - прибавляет 1 к аргументу: |x⇐ |x+1
В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии
F(x,y) = R( g1, f3), требовалась м.Т.
M2, которая переводит конфигурацию вида
|y *|x* |u* |z в конфигурацию
|y *|x* |u+1* |f(x,u,z) , используя м.Т.
Mf, вычисляющую функцию f(x,u,z).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для
M2 ?
P1 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, Пуст, Mf ); Зам( #,* ); Зам( #,* )P2 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, Пуст, Mf ); par# (Пуст, par* (Пуст, +1, Чист), Пуст); Зам( #,* ); Зам(∧, |); Зам( #,| ); par* (Пуст, Пуст, Пуст, Выч1; Выч1)P3 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, par* (Пуст, +1, Чист), Mf ); par* (Зам( #,* ), Пуст, Зам(∧, |); Зам( #,| ); Выч1; Выч1)
В этих определениях участвуют следующие простые машины Тьюринга:
Копa –копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст - не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧);+1 - прибавляет 1 к аргументу: |x⇐ |x+1