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