Главная /
Введение в схемы, автоматы и алгоритмы /
Приведенные ниже машины Тьюринга 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) = 3x
в унарном кодировании, т.е. переводит вход |x в выход |y, где y = 3x
?
вопрос
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
ни одна
Сложность вопроса
73
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Какой студент ищет эти вопросы интуит? Это же крайне просто
28 дек 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ? (a) является отношением эквивалентности,(b) рефлексивно и транзитивно,(c) сохраняет свойство разрешимости: если A ≤ m B и B - разрешимо, то и A разрешимо.
- # Пусть задана линейная программа P со входными переменными X1, X2, X3: Y = X1 ∨ X2; Z = X1 ∨ X3; U = ¬X3;Y = Y ∧ Z;W = X2 ∨ X3; U = X2 ∨ U; Z = W ∨ Y ; Z = U ∧ Y. Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конецP2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конецP3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все
- # Пусть функция F(x) задана примитивной рекурсией R(1, h(y,z)), где h(y,z) = [2z/z2]Чему равно значение F(5)?
- # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа x, отличных от 1 и самого x?