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