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