Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:

В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?

Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1100 ?

Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?

В доказательстве теоремы 20.2 для построения м.Т M_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M⁴³, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M⁴³ ?(В текстах программ 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_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M²⁴, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M²⁴ ?(В текстах программ 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_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M³¹, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M³¹ ?(В текстах программ 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 w₁ #^k#' (a ∈Σ, w₁ ∈Σ*, k ≥ 0), должна завершить работу в конфигурации ∧^kpa'w₁ Пусть алфавит ленты MOVE включает символы из Σ ∪ {a' | a ∈ Σ}∪ {∧, #, #'}, а алфавит состояний Q= {q, p, r} ∪ {p^a | a ∈ Σ}Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для MOVE ?(В текстах программ a и b – это произвольные символы из Σ),

P1: q a →​ p^a ∧ П , q a' →​ p a' Н , p^a b →​ p^b a П, p^a b' →​ p^b a' П, p^a # →​ r a Л, p^a #' →​ r a' Л, p^a ∧ →​ r a Л, r a →​ r a Л , r a' →​ r a' Л , r ∧ →​ q ∧ П.

P2: q a →​ p^a ∧ П , p^a b →​ p^b a П, p^a b' →​ p^b a' П, p^a # →​ r a Л, p^a #' →​ r a' Л, p^a ∧ →​ r a Л, r a →​ r a Л , r a' →​ r a' Л , r ∧ →​ q ∧ П.

P3: q a →​ p^a ∧ П , p^a b →​ p^a b П, p^a # →​ p^a # П, p^a #' →​ r a Л, p^a b' →​ p^a b' П, p^a ∧ →​ r a Л, r a →​ r a Л , r a' →​ r a' Л , r ∧ →​ q ∧ П, q # →​ q ∧ П , q a' →​ p a' Н.

Три машины Тьюринга M_i = < Σ, Q !, P_i, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q aⁿ b в заключительную конфигурацию ! b a²ⁿ (n ≥ 0 )?

Три машины Тьюринга M_i = < Σ, Q !, P_i, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q a²ⁿ b в заключительную конфигурацию ! b aⁿ (n ≥ 0 )?

В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов ∧, * и # , q – начальное состояние) в конфигурациюy* q’ x (q' – заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {p^a | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ?(В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {*, #} ).

P1: q b →​ q b П , q ∧ →​ s # Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ p^a ∧П, p * →​ r ∧П, p^a b →​ p^a b П, p^a ∧ →​ s a Л, r a →​ r a П , r # →​ q’ * П.

P2: q a →​ q a П , q ∧ →​ s * Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ p^a ∧П, p * →​ r ∧П, p^a b →​ p^a b П, p^a ∧ →​ s a Л, r a →​ r a П , r*→​ q’ * П.

P3: q a →​ q a П , q ∧ →​ s * Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ p^a ∧П, p * →​ q’ * П, p^a b →​ p^a b П, p^a ∧ →​ s a Л.

Три машины Тьюринга M_i = < Σ, Q !, P_i, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q aⁿ b в заключительную конфигурацию ! b aⁿ (n ≥ 0 )?