КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Доказательство. Рассмотрим вопрос о существовании такого алгоритма, который для произвольной программы и начальных данных для нее позволяет ответить на вопрос:
ТЕОРЕМА 8.4 ПРОБЛЕМА ОСТАНОВКИ
Рассмотрим вопрос о существовании такого алгоритма, который для произвольной программы и начальных данных для нее позволяет ответить на вопрос: "заканчивается работа программы на заданных исходных данных за конечное число шагов или нет?". Сформулированная задача называется проблемой остановки. Переформулируем эту проблему в терминах разрешимости множеств. Всякую программу будем рассматривать как представление алгоритма, вычисления значений числовой функции. Для определенности будем считать, что программы представлены в виде конечной последовательности задающих их текстов. Начальные данные для программы P будем представлять натуральными числами. Тогда можно считать, что программа с текстом P вычисляет одноместную числовую функцию Определим множество: R1 = {(m, n) | значение fm (n) определено}. Нетрудно видеть, что если существует алгоритм, который по произвольной программе P и некоторому начальному данному d для этой программы определяет, заканчивается ли вычисление программы P на d или нет, то множество R 1 является разрешимым. Покажем, что множество R1 не является разрешимым. Из этого будет следовать неразрешимость проблемы остановки.
Множество R 1 неразрешимое. Предположим противное. Пусть характеристическая функция множества R 1: (x 1, x 2)= является вычислимой. Поскольку - вычислимая, то вычислима и функция g (x) = (x, x). Определим вспомогательную функцию:
d (x) = . Функция d называется диагональной. Для каждого значения своего аргумента, равного x, она определена тогда и только тогда, когда значение fx (x) не определено.
То есть d отлична от любой функции последовательности (3) всех одноместных частично-рекурсивных функций. С другой стороны d получается из вычислимой числовой функции с помощью программно реализуемых (вычислимых) операций и поэтому является вычислимой. Следовательно, d должна совпадать с одной из функций в последовательности всех одноместных частично-рекурсивных функций (3). Полученное противоречие означает, что предположение о разрешимости множества R1 является неверным. Следовательно, R1 - это неразрешимое множество.
Дата добавления: 2015-03-31; Просмотров: 368; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |