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

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

Номер 1

  В доказательстве теоремы 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

Ответ:

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) все

(6) ни одна

Номер 2

  В доказательстве теоремы 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

Ответ:

(1) только P1

(2) только P2

(3) только P3

(4) P2 и P3

(5) P1 и P3

(6) ни одна

Номер 3

  В доказательстве теоремы 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

Ответ:

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) все

(6) ни одна

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

Номер 1

  В доказательстве теоремы 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, ∧>  П.

Ответ:

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

Номер 2

  В доказательстве теоремы 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 < ∧, ∧, ∧, ∧> П.

Ответ:

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

Номер 3

  В доказательстве теоремы 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 > Л ,

Ответ:

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

Номер 1

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?
(а) рефлексивность: A ≤m A ,
(b) симметричность: A ≤m B  ⇔ B ≤m A,
(с) транзитивность:  A ≤m B  и B ≤m C  ⇐  A ≤m C .

Ответ:

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) всеми

Номер 2

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?
(a)    является отношением эквивалентности,
(b)    рефлексивно и транзитивно,
(c)    сохраняет свойство разрешимости: если  A ≤ m B  и B  - разрешимо, то и   A  разрешимо.

Ответ:

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) всеми

Номер 3

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?                                     
(a)    если A ≤m B, то (N \A)  ≤m (N \B)  , 
(b)    A ≤m C и B ≤m C  для  C= {2x | x ∈ A} ∪ {2x+1 | x ∈ B},
(c)    сохраняет свойство неразрешимости: если  A ≤m B и A  - неразрешимо, то и   B   неразрешимо .

Ответ:

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) всеми

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

Номер 1

 Пусть множество A = { (x, y) | y = x² }, B = { n³ | n ∈ N }.
Какие из следующих функций осуществляют сведение A ≤m B ? 
(В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 и sg(n) = 1 при n > 0).

Ответ:

(1) f(x,y) = x³

(2) f(x,y) = x³ + sg( | x² – sqr(y)² |)

(3) f(x,y) = (x+1)³ + sg( | x² – sqr(y)² |)

(4) f(x,y) = (x+1)³ + | x² – y |

(5) f(x,y) = 1 + sg(| x² – y |)

Номер 2

 Пусть множество A = { (x², y²) | x ∈ N , y ∈ N  }, B = { n³ | n ∈ N }.
Какие из следующих функций осуществляют сведение A ≤m B ? 
(В выражениях ниже sqr(x) обозначает целую часть квадратного корня из x, sg(0) =0 и
sg(n) = 1 при n > 0).

Ответ:

(1) f(x,y) = x³y³

(2) f(x,y) = (x+2)³ + sg( x² – sqr(x)² ) + sg( y² – sqr(y)² )

(3) f(x,y) = 8 + sg( x² – sqr(x)² + y² –sqr(y)² )

(4) f(x,y) = sqr(x)³ sqr(y)³

(5) f(x,y) = (sqr(x) + sqr(y))³

Номер 3

 Пусть множество A = { (x, y) | y = x² }, B = { 2ⁿ | n ∈ N }.
Какие из следующих функций осуществляют сведение A ≤m B ? 
(В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 и
sg(n) = 1 при n > 0).

Ответ:

(1) f(x,y) = 2^x

(2) f(x,y) = 2^x+1 + sg( | x² – sqr(y)² |)

(3) f(x,y) = 4 + sg( | x² – y |)

(4) f(x,y) = 2^x + | x² – y |

(5) f(x,y) = 1 + sg(| x² – y |)

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

Номер 1

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.

(a) x := x+1, (b) x := 0, (c) x := y.

Ответ:

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) Любой из них

Номер 2

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным.  Некоторые из операторов  языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.
Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.
(a)    если  x < y  то P1 иначе P2 конец,
(b)    если  x = y  то P1 иначе P2 конец.,
(c)    x := 0.

Ответ:

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) Любой из них

Номер 3

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным.  Некоторые из операторов  языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.
Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.
(a)    x := x +1,
(b)    пока  x < y  делай P все,
(c)    пока  x = y  делай P все.
.

Ответ:

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) Любой из них

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

Номер 1

 В теореме 20.5 была доказана неразрешимость проблемы останова:
по произвольной структурированной программе П  определить завершится ли вычисление П на входе 0. Пусть M_h0= {n  |  Ф_Пn,y(0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе независимости ее результата от входа: 
M_const= {n  |  существует константа c ∈ N такая, что  Ф_Пn,y(x) = c для всех x}.
Какие из следующих функций сводят M_h0 к M_const ?
f1(n) = номер программы: ' x:= 0; П_n ; y:= 0'. 
f2(n) = номер программы: 'П_n ; y:= x'. 
f3(n) = номер программы: ' x:= 0; П_n ; y:= 0; y:= y+1'.

Ответ:

(1) только f1

(2) только f2

(3) только f3

(4) f1 и f2

(5) f1 и f3

(6) все

Номер 2

 В теореме 20.5 была доказана неразрешимость проблемы останова:
по произвольной структурированной программе П  определить завершится ли вычисление П на входе 0. Пусть M_h0= {n  |  Ф_Пn,y(0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе бесконечности множества ее результатов: 
M_inf= {n  |  множество значений  Ф_Пn,y(x) бесконечно}.
Какие из следующих функций сводят M_h0 к  M_inf ?
f1(n) = номер программы: ' x:= 0; П_n ; y:= x '. 
f2(n) = номер программы: 'x_n:=x; x:= 0;  П_n ; y:= x_n'. (здесь переменная x_n не входит в П_n )
f3(n) = номер программы: 'y:= x; x:= 0; П_n ; y:= y+1'.

Ответ:

(1) только f1

(2) только f2

(3) только f3

(4) f1 и f2

(5) f1 и f3

(6) все

Номер 3

 В теореме 20.5 была доказана неразрешимость проблемы останова:
по произвольной структурированной программе П  определить завершится ли вычисление П на входе 0. Пусть M_h0= {n  |  Ф_Пn,y(0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе монотонности вычисляемой ею функции:
M_mon= {n  |  для любых x1 и x2, если x1 < x2, то  Ф_Пn,y(x1) <  Ф_Пn,y(x2)}.
Какие из следующих функций сводят M_h0 к  M_mon?
f1(n) = номер программы: 'x_n:=x; x:= 0;  П_n ; y:= x_n'. (здесь переменная x_n не входит в П_n ) 
f2(n) = номер программы: 'П_n ; y:= x'. 
f3(n) = номер программы: 'y:= x; x:= 0; П_n ; y:= y+1'.

Ответ:

(1) только f1

(2) только f2

(3) только f3

(4) f1 и f2

(5) f1 и f3

(6) все

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