Пусть машина Тьюринга
M построена из простых машин Тьюринга
Копa , Зам(a, b), Сум, Умн и
Пуст, описанных в задаче 4, и машин
Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:
M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );if Больше21 then par#( Пуст, Сум ) else par#( Пуст, Умн ) endif;Зам(#, *); Выб33.
Какие результаты она получит на входных данных вида
|x1 * |x2при x1 = 2, x2 = 7 и при
x1 = 3, x2 = 5, соответственно?
Пусть машина Тьюринга
M построена из простых машин Тьюринга
Копa , Зам(a, b), Сум, Умн и
Пуст, описанных в задаче 4, и машин
Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:
M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );if Больше21 then par#( Пуст, Умн ) else par#( Пуст, Сум ) endif;Зам(#, *); Выб33.
Какие результаты она получит на входных данных вида
|x1 * |x2при x1 = 4, x2 = 8 и при
x1 = 1, x2 = 5, соответственно?
Приведенные ниже машины Тьюринга
Mi (i= 1,2,3,4)M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 M3 = if Нуль11 then Пуст else Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Умн); Зам(#, *)) enddo; Выб33 endif.
M4 = if Нуль11 then Пуст else Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Сум); Зам(#, *)) enddo; Выб33 endif.
построены из простых машин Тьюринга
Копa , Зам(a, b), Сум, Умн и
Пуст, описанных в задаче 4, и машин
Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧)
Какая из этих машин вычисляет функцию
f(x) = xx в унарном кодировании, т.е. переводит вход
|x в выход
|y, где
y = xx (пусть
f(0)=0) ?
Пусть машина Тьюринга
M построена из следующих простых машин Тьюринга:
Копa –копирует вход после разделительного символа
a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ;Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy ;Пуст - не изменяет аргумент: w ⇐ w
с помощью операций последовательного и параллельного применения следующим образом:
M = Коп# ; par#( Коп* ; Умн, Пуст ); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум
Какую из следующих арифметических функций
f(x) (при унарном кодировании аргумента и результата) вычисляет
M?
Приведенные ниже машины Тьюринга
Mi (i= 1,2,3,4)M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 M3 = if Нуль11 then Пуст else Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Умн); Зам(#, *)) enddo; Выб33 endif.
M4 = if Нуль11 then Пуст else Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Сум); Зам(#, *)) enddo; Выб33 endif.
построены из простых машин Тьюринга
Копa , Зам(a, b), Сум, Умн и
Пуст, описанных в задаче 4, и машин
Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i, i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧)
Какая из этих машин вычисляет функцию
f(x) = 3x в унарном кодировании, т.е. переводит вход
|x в выход |y, где y = 3x?
Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)
M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 M3 = if Нуль11 then Пуст else Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Умн); Зам(#, *)) enddo; Выб33 endif.
M4 = if Нуль11 then Пуст else Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Сум); Зам(#, *)) enddo; Выб33 endif.
построены из простых машин Тьюринга
Копa , Зам(a, b), Сум, Умн и
Пуст, описанных в задаче 4, и машин
Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧)
Какая из этих машин вычисляет функцию
f(x) = 2x в унарном кодировании, т.е. переводит вход
|x в выход |y, где
y = 2x?
В доказательстве теоремы 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
Пусть машина Тьюринга
M построена из следующих простых машин Тьюринга:
Копa –копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ;Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy ;Пуст - не изменяет аргумент: w ⇐ w
с помощью операций последовательного и параллельного применения следующим образом:
M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум
Какую из следующих арифметических функций
f(x) (при унарном кодировании аргумента и результата) вычисляет
M?
В доказательстве теоремы 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