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

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

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

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

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

Варианты ответа
только M2
M1 и M3(Верный ответ)
ни одна
M2 и M3
M1 и M2
только M3
только M1
Похожие вопросы
Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b a2n (n ≥ 0 )?
Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b an (n ≥ 0 )?
В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов , * и # , q – начальное состояние) в конфигурациюy* q’ x (q' – заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {pa | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ?(В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {*, #} ).

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

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

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

В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M43 ?(В текстах программ 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П, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M24 ?(В текстах программ 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П, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M31, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M31 ?(В текстах программ 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 < ∧, ∧, ∧, ∧> П.
  • Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов и *, но головка "заблудилась" – она наблюдает символ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧k w или w∧k q ∧ (k > 0) переведут в конфигурацию q'w ?(В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l1, r1 , l2 , r2, l3, r3, l4)

    P1: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 a→​ l2 a Л, l2 ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л, r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.

    P2: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 ∧→​ l2∧ П, l2 *→​ l3∧ Л, l3 ∧→​ l3∧ Л, l3 a→​ q'a Н,r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л,r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.

    P3: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 ∧→​ l2∧ П, l2 *→​ l3∧ Л, l3 ∧→​ l3∧ Л, l3 a→​ l4 a Л,l4 a→​ l4 a Л, l4 ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л,r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.

    В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее MOVE, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее, MOVE, начав работать в конфигурации вида q a w1 #k#' (a ∈Σ, w1 ∈Σ*, k ≥ 0), должна завершить работу в конфигурации kpa'w1 Пусть алфавит ленты MOVE включает символы из Σ ∪ {a' | a ∈ Σ}∪ {∧, #, #'}, а алфавит состояний Q= {q, p, r} ∪ {pa | a ∈ Σ}Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для MOVE ?(В текстах программ a и b – это произвольные символы из Σ),

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

    P2: q a →​ pa ∧ П , pa b →​ pb a П, pa b' →​ pb a' П, pa # →​ r a Л, pa #' →​ r a' Л, pa ∧ →​ r a Л, r a →​ r a Л , r a' →​ r a' Л , r ∧ →​ q ∧ П.

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

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