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