Главная
Проблема исчисления предикатов
Процедура унификации
Отношения на функциях принадлежности
Неразрешимые алгоритмические проблемы МТ
Полнота и непротиворечивость
NP-полные (универсальные) задачи
Стандартизация услуг
Стандартизация и экология
Организационные и методические принципы сертификации в России
Программа сертификации
Метрологический надзор
Структура кристаллов
Судьбы крестьянские
Еще одна фальшивая ценность
Такая судьба
Соприкосновение с рынком
Мой театр, мои коллеги
Гастроли
И жизнь и слезы и любовь
Возвращение из Томска
Реклама:
|
|
Неразрешимые алгоритмические проблемы МТ
адающая следующим свойством: если записать на ее ленте систему команд произвольной МТ T и произвольное слово в алфавите данных Т, то она переработает это слово также, как переработала бы Т.
Иначе говоря, нам необходима машина, которая работала бы за любую МТ. Такую МТ естественно назвать универсальной.
Таким образом, если есть МТ Т с системой команд ?T , причем Т(a)=w, то Универсальная Машина Тьюринга (УМТ) должна делать следующее: Tу(?T|a)=?T|w, где “|” – разделитель кода от данных.
Для реализации такой МТ необходимо слева от разделителя вписать все команды МТ Т. Справа от разделителя необходимо расположить ее данные, причем в определенной ячейке данных, будет стоять символ, означающий текущее состояние qi МТ Т, а следующ
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
