База ответов ИНТУИТ

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

<<- Назад к вопросам

Приведенные ниже машины Тьюринга 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?

    (Отметьте один правильный вариант ответа.)

    Варианты ответа
    M2(Верный ответ)
    M4
    ни одна
    M3
    M1
    Похожие вопросы
    Приведенные ниже машины Тьюринга 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) ?
    Приведенные ниже машины Тьюринга 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?
    В доказательстве теоремы 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
  • Пусть машина Тьюринга 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, соответственно?
    Пусть машина Тьюринга 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  Больше12  then par#(  Пуст, Сум  ) else  par#(  Пуст, Умн ) endif;Зам(#, *); Выб33.
    Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 3, x2 = 6 и при x1 = 2, x2 = 6, соответственно?
    В доказательстве теоремы 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
  • В доказательстве теоремы 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
  • Пусть машина Тьюринга 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?
    Пусть машина Тьюринга 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?