Главная /
Введение в схемы, автоматы и алгоритмы /
Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4) M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) end
Приведенные ниже машины Тьюринга 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
?
вопрос
M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22
M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22
Выбin
– выбирает i
-ый аргумент из n
аргументов: x1*…*xi*…*xn ⇐ xi
,Нульin
- выдает 1, если i
-ый аргумент из n
аргументов равен ∧
(нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0
),Выч1
– вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧)
Правильный ответ:
M1
M2
M3
M4
ни одна
Сложность вопроса
86
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень намудрённый вопрос интуит.
03 апр 2018
Аноним
Если бы не данные решения - я бы не решил c этими тестами интуит.
01 июл 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Чему равна глубина схемы S1, реализующей функцию сложения однобитовых чисел?
- # Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?
- # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?
- # Предположим, что в некоторой конфигурации машины Тьюринга 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 Н.