Главная /
Введение в схемы, автоматы и алгоритмы /
Приведенные ниже машины Тьюринга 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) = xx
в унарном кодировании, т.е. переводит вход |x
в выход |y
, где y = xx
(пусть f(0)=0
) ?
вопрос
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
ни одна
Сложность вопроса
85
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Экзамен сдал на зачёт. спс
04 сен 2016
Аноним
Экзамен сдан на 4. Спасибо vtone
21 ноя 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x +1,(b) пока x < y делай P все,(c) пока x = y делай P все. .
- # Чему равна глубина схемы Sodd , реализующей функцию odd(X1, X2, …,Xn) = X1 + X2 + … Xn ?
- # Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- # Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, [Большая Картинка] Какой из следующих языков распознает автомат A ?
- # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { a2bna2 | n > 0 }, L2 = { ww | w = a2bna2 , n > 0 }, L3 = { wv | w = a2bna2 , v = b2amb2 для произвольных n,m > 0 }.