Пусть машина Тьюринга
M имеет алфавит ленты
Σ={ ∧, 0, 1}, алфавит состояний
Q= {q, p, r, !}, начальное состояние
q, заключительное состояние
! и программу
Ф:
В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации
q 1010 ?
Пусть машина Тьюринга
M имеет алфавит ленты
Σ={ ∧, 0, 1}, алфавит состояний
Q= {q, p, r, !}, начальное состояние
q, заключительное состояние
! и программу
Ф:
В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации
q 1010 ?
В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M24 ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})P1: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, |, c, ∧> → q <a, ∧ , c, ∧> П , s <∧, ∧, ∧, ∧> → p <∧, ∧ , ∧, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,P2: q <a, |, c, d> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, ∧, c, |> → q <a, ∧ , c, ∧> П , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,P3: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, b, c, ∧> → s <a, ∧ , c, ∧> Л , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П.
В доказательстве теоремы 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 < ∧, ∧, ∧, ∧> П.
В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее
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' Н.
Три машины Тьюринга
Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты
Σ={ ∧, a, b}, алфавит состояний
Q = { q, p, r, s, !}, начальное состояние
q, заключительное состояние
! и следующие программы:
Какие из этих машин переводят любую начальную конфигурацию вида
q an b в заключительную конфигурацию
! b a2n (n ≥ 0 )?
Три машины Тьюринга
Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты
Σ={ ∧, a, b}, алфавит состояний
Q = { q, p, r, s, !}, начальное состояние
q, заключительное состояние
! и следующие программы:
Какие из этих машин переводят любую начальную конфигурацию вида
q a2n b в заключительную конфигурацию
! b an (n ≥ 0 )?
В конструкции для параллельной композиции машин Тьюринга на этапах 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 Л.
Три машины Тьюринга
Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты
Σ={ ∧, a, b}, алфавит состояний
Q = { q, p, r, s, !}, начальное состояние
q, заключительное состояние
! и следующие программы:
Какие из этих машин переводят любую начальную конфигурацию вида
q an b в заключительную конфигурацию
! b an (n ≥ 0 )?