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