Введение в схемы, автоматы и алгоритмы

Упражнение 1:

Номер 1

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

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

Ответ:

(1) ! 0101

(2) ! 0110

(3) ! 1001

(4) ! 1110

(5) ни в одну из выше указанных

Номер 2

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

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

Ответ:

(1) ! 1011

(2) ! 0110

(3) ! 0011

(4) ! 1110

(5) ни в одну из выше указанных

Номер 3

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

Ответ:

(1) ! 1100

(2) ! 0101

(3) ! 1001

(4) ! 1101

(5) ни в одну из выше указанных

Упражнение 2:

Номер 1

 Три машины Тьюринга 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 )?

Ответ:

(1) только M₁

(2) только M₂

(3) только M₃

(4) M₁ и M₂

(5) M₁ и M₃

(6) M₂ и M₃

(7) ни одна

Номер 2

 Три машины Тьюринга 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 )?

Ответ:

(1) только M₁

(2) только M₂

(3) только M₃

(4) M₁ и M₂

(5) M₁ и M₃

(6) M₂ и M₃

(7) ни одна

Номер 3

 Три машины Тьюринга 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 )?

Ответ:

(1) только M₁

(2) только M₂

(3) только M₃

(4) M₁ и M₂

(5) M₁ и M₃

(6) M₂ и M₃

(7) ни одна

Упражнение 3:

Номер 1

В конструкции для параллельной композиции машин Тьюринга на этапах 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 Л.

Ответ:

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

Номер 2

Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧^k w или w∧^kq ∧ (k > 0) переведут в конфигурацию q'w ? (В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l₁, r₁ , l₂, r₂, l₃, r₃, l₄)

P1: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂a→ l₂ a Л, l₂∧→ q'∧ П, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

P2: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂*→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ q'a Н, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

P3: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂*→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ l₄ a Л, l₄a→ l₄ a Л, l₄∧→ q'∧ П, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

Ответ:

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

Номер 3

В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее 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' Н.

Ответ:

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

Упражнение 4:

Номер 1

 Пусть  машина Тьюринга M построена из следующих простых машин Тьюринга:
Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Сум        - складывает два аргумента в унарной системе: |^x * |^y ⇐  |^x+y ;
Умн        - умножает два аргумента в унарной системе: |^x * |^y ⇐  |^xy;
с помощью операций последовательного и параллельного применения следующим образом:
M =  Коп_# ; par_#( Коп_* , Коп_* ); par_#( Умн, Сум); Зам(#, *); Сум
Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

Ответ:

(1) f(x) = 2x² + 2x

(2) f(x) = x² + x

(3) f(x) = 2x² + x

(4) f(x) = x² + 2x

(5) ни одну из выше перечисленных

Номер 2

 Пусть  машина Тьюринга M построена из следующих простых машин Тьюринга:
Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Сум        - складывает два аргумента в унарной системе: |^x * |^y ⇐  |^x+y ;
Умн        - умножает два аргумента в унарной системе: |^x * |^y ⇐  |^xy ;
Пуст       - не изменяет аргумент: w ⇐ w
с помощью операций последовательного и параллельного применения следующим образом:
M =  Коп_# ; par_#( Коп_* , Коп_* ); par_#( Умн, Сум); par_#( Коп_* ; Сум  , Пуст ); Зам(#,?); Сум
Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

Ответ:

(1) f(x) = 2x² + 2x

(2) f(x) = x² + x

(3) f(x) = 2x² + x

(4) f(x) = x² + 2x

(5) ни одну из выше перечисленных

Номер 3

 Пусть  машина Тьюринга M построена из следующих простых машин Тьюринга:
Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Сум        - складывает два аргумента в унарной системе: |^x * |^y ⇐  |^x+y ;
Умн        - умножает два аргумента в унарной системе: |^x * |^y ⇐  |^xy ;
Пуст       - не изменяет аргумент: w ⇐ w

с помощью операций последовательного и параллельного применения следующим образом:
M =  Коп_# ; par_#( Коп_* ; Умн, Пуст ); par_#( Коп_* ; Сум  , Пуст );  Зам(#,?); Сум
Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

Ответ:

(1) f(x) = 2x² + 2x

(2) f(x) = x² + x

(3) f(x) = 2x² + x

(4) f(x) = x² + 2x

(5) ни одну из выше перечисленных

Упражнение 5:

Номер 1

Пусть  машина Тьюринга M построена из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн  и Пуст, описанных в задаче 4, и машин
Выб_in – выбирает i-ый аргумент из  n аргументов: x₁*…*x_i*…*x_n  ⇐ x_i ,
Больше_ij - выдает 0, если в аргументе вида |^x1 *…*|^xi *…*|^xj *…*|^xn  i-ый аргумент xi больше j-ого аргумента xj , иначе  выдает 1,
с помощью операций последовательного и параллельного применения и конструкции условного оператора  следующим образом:

M =  Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст );
if  Больше₁₂  then par_#(  Пуст, Сум  ) else  par_#(  Пуст, Умн ) endif;
Зам(#, *); Выб_33.

Какие результаты она получит на входных данных вида  |^x1 * |^x2 при  x₁= 3, x₂= 6 и при  x₁= 2, x₂= 6, соответственно?

Ответ:

(1) 9 и 8

(2) 18 и 12

(3) 9 и 12

(4) 18 и 8

(5) ни один из предыдущих ответов не подходит

Номер 2

Пусть  машина Тьюринга M построена из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн  и Пуст, описанных в задаче 4, и машин
Выб_in – выбирает i-ый аргумент из  n аргументов: x₁*…*x_i*…*x_n  ⇐ x_i ,
Больше_ij - выдает 0, если в аргументе вида |^x1 *…*|^xi *…*|^xj *…*|^xn  i-ый аргумент xi больше j-ого аргумента xj , иначе  выдает 1,
с помощью операций последовательного и параллельного применения и конструкции условного оператора  следующим образом:

M =  Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст );
if  Больше₂₁  then par_#(  Пуст, Сум  ) else  par_#(  Пуст, Умн ) endif;
Зам(#, *); Выб_33.

Какие результаты она получит на входных данных вида  |^x1 * |^x2
при  x₁= 2, x₂= 7 и при  x₁= 3, x₂= 5, соответственно?

Ответ:

(1) 9 и 8

(2) 9 и 15

(3) 14 и 8

(4) 14 и 15

(5) ни один из предыдущих ответов не подходит

Номер 3

Пусть  машина Тьюринга M построена из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн  и Пуст, описанных в задаче 4, и машин
Выб_in – выбирает i-ый аргумент из  n аргументов: x₁*…*x_i*…*x_n  ⇐ x_i ,
Больше_ij - выдает 0, если в аргументе вида |^x1 *…*|^xi *…*|^xj *…*|^xn  i-ый аргумент xi больше j-ого аргумента xj , иначе  выдает 1,
с помощью операций последовательного и параллельного применения и конструкции условного оператора  следующим образом:

M =  Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст );
if  Больше₂₁  then par_#(  Пуст, Умн ) else  par_#(  Пуст, Сум ) endif;
Зам(#, *); Выб_33.

Какие результаты она получит на входных данных вида  |^x1 * |^x2
при  x₁= 4, x₂= 8 и при  x₁= 1, x₂= 5, соответственно?

Ответ:

(1) 12 и 5

(2) 12 и 6

(3) 32 и 5

(4) 32 и 6

(5) ни один из предыдущих ответов не подходит

Упражнение 6:

Номер 1

Приведенные ниже машины Тьюринга Mi  (i= 1,2,3,4)
M1 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; Зам(#, |); Выч1) enddo;  Выб₂₂
M2 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; par_# (Пуст, Коп_#);  Зам(#, |); Зам(#, |); Выч1; Выч1) enddo;  Выб₂₂

M3 =   if  Нуль₁₁ then Пуст 
            else  Коп_*Зам(∧, *); Зам(∧,|); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст); 
             par_# (Пуст, Умн);  Зам(#, *)) enddo;  Выб₃₃ endif.

M4 =   if  Нуль₁₁ then Пуст 
            else  Коп_*Зам(∧, *); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст); 
            par_# (Пуст, Сум);  Зам(#, *)) enddo;  Выб₃₃ endif.
построены из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн  и Пуст, описанных в задаче 4, и машин
Выб_in – выбирает i-ый аргумент из  n аргументов: x₁*…*x_i*…*x_n  ⇐ x_i ,
Нуль_in - выдает 1, если i-ый аргумент из  n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ,  i >0),
Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1   (| ⇐ ∧)

Какая из этих машин вычисляет функцию f(x) = 3^x в унарном кодировании, т.е. переводит вход |^x в выход |^y, где y = 3^x?

Ответ:

(1) M1

(2) M2

(3) M3

(4) M4

(5) ни одна

Номер 2

Приведенные ниже машины Тьюринга Mi  (i= 1,2,3,4)

M1 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; Зам(#, |); Выч1) enddo;  Выб₂₂
M2 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; par_# (Пуст, Коп_#);  Зам(#, |); Зам(#, |); Выч1; Выч1) enddo;  Выб₂₂

M3 =   if  Нуль₁₁ then Пуст 
            else  Коп_*Зам(∧, *); Зам(∧,|); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст); 
            par_# (Пуст, Умн);  Зам(#, *)) enddo;  Выб₃₃ endif.

M4 =   if  Нуль₁₁ then Пуст 
            else  Коп_*Зам(∧, *); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст); 
            par_# (Пуст, Сум);  Зам(#, *)) enddo;  Выб₃₃ endif.
построены из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн  и Пуст, описанных в задаче 4, и машин
Выб_in – выбирает i-ый аргумент из  n аргументов: x₁*…*x_i*…*x_n  ⇐ x_i ,
Нуль_in - выдает 1, если i-ый аргумент из  n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ , i >0),
Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1   (| ⇐ ∧)

Какая из этих машин вычисляет функцию f(x) = 2^x в унарном кодировании, т.е. переводит вход |^x в выход |^y, где y = 2^x?

Ответ:

(1) M1

(2) M2

(3) M3

(4) M4

(5) ни одна

Номер 3

Приведенные ниже машины Тьюринга Mi  (i= 1,2,3,4)

M1 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; Зам(#, |); Выч1) enddo;  Выб₂₂
M2 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; par_# (Пуст, Коп_#);  Зам(#, |); Зам(#, |); Выч1; Выч1) enddo;  Выб₂₂

M3 =   if  Нуль₁₁ then Пуст 
            else  Коп_*Зам(∧, *); Зам(∧,|); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст); 
            par_# (Пуст, Умн);  Зам(#, *)) enddo;  Выб₃₃ endif. 

M4 =   if  Нуль₁₁ then Пуст 
            else  Коп_*Зам(∧, *); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст); 
            par_# (Пуст, Сум);  Зам(#, *)) enddo;  Выб₃₃ endif.

построены из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн  и Пуст, описанных в задаче 4, и машин
Выб_in – выбирает i-ый аргумент из  n аргументов: x₁*…*x_i*…*x_n  ⇐ x_i ,
Нуль_in - выдает 1, если i-ый аргумент из  n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ , i >0),
Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1   (| ⇐ ∧,  ∧ ⇐ ∧)
Какая из этих машин вычисляет функцию f(x) = x^x в унарном кодировании, т.е. переводит вход |^x в выход |^y, где y = x^x (пусть f(0)=0) ?

Ответ:

(1) M1

(2) M2

(3) M3

(4) M4

(5) ни одна

Введение в схемы, автоматы и алгоритмы - тест 9