Вопрос 20. Теорема Райса.
Теорема 2.6. Никакое нетривиальное свойство вычислимой функции не является алгоритмически разрешимым. Доказательство:
1. Определим понятие нетривиальное свойство вычислимой функции. Пусть С — некоторый класс вычислимых функций, нетривиальный в том смысле, что имеются функции принадлежащие и не принадлежащие классу С. Одну и туже вычислимую функцию можно реализовать множеством МТ (таких МТ счетное количество).
Переформулируем теорему — не существует алгоритм который по описанию некоторой МТ Т( x ) определял бы, принадлежит ли функция вычисляемая этой МТ Т, некоторому классу функций С или нет.
2. Предположим, что такой алгоритм Tc существует, где Tc — знак некоторой МТ. Тогда, по условию теоремы можно записать, что Tc исследует некоторую МТ и реализует = { Истина, если функция Т(x)?С и Лож , если функция Т(x) ? С , где Т некоторая или любая МТ вычисляющая Т( x ).
3. Построим вспомогательную МТ Т| (вычислимую по Тьюрингу ) для заданной МТ Т и любых данных Х. T| (T, x) = {fc (x), если Т(x) останавливается, f0 (x), если T(x) не останавливается.
Т| является УМТ, которая игнорирует результаты вычисления Т(x), а в место нее вычисляет значение некоторой функции из класса С. Добавляем в системе команд МТ Т| систему команд, вычисляющую нигде не определенную функцию f0. fc (x) — функция принадлежащая классу С.
Т.к. Т (x) и fc (x) являются вычислимыми (Т| является разветвлением функции f0 и fc по заключительному состоянию Т(x) ) и Т| существует, т.к. существует УМТ.
4. Построим вспомогательную машину Т|| для чего зафиксируем данные X для T| . Для любого Х строим Т|| (Т). Т|| сначала записывает на ленту некоторую фиксированную строку Х , а затем запускает машину Т| . Т|| (T) = T(x) Т| (T, x ) и такую машину можно построить.
5. Применим Т|| (Т) в качестве исходных данных для машины Tc. Машина Т|| вычисляет функцию класса С, но тогда Tc (Т||) = {И, если Т(x) останавливается; Л, если Т(x) не останавливается.
6. В результате использования конструктивных средств при построении МТ Т|| получили МТ TC решающую проблему остановки, что невозможно. Следовательно предположение машины TC неверно.
Выводы: 1) По описанию МТ нельзя узнать, вычисляет ли она функцию, которая постоянная, периодическая, ограниченная, содержит ли она среди своих значений данное число, определенна ли эта функция в некоторой точке. 2) По описанию алгоритма ничего нельзя узнать о свойстве функции которую он вычисляет. Одна и та же функция может быть вычислена различными алгоритмами, которых счетное количество. 3) Неразрешима проблема эквивалентности алгоритма. По двум заданным алгоритмам нельзя узнать вычисляют ли они одну и туже функцию или нет. 4) Ничего нельзя узнать о вычислимой функции —преувеличение. Точная формулировка о неразрешимости должна содержать фразу: “Не существует единого алгоритма позволяющего узнать …”. 5) В теореме Райса речь идет о невозможности распознавания свойств вычислимых свойств на универсальном алгоритм. Языке (МТ, С, Паскаль, …). Свойства подклассов вычислимых функций, записанных в специальных языках вполне могут оказаться разрешимыми. 6) Противоречит ли Т Райса практике программирования. Опыт программиста т Райса не должна удивлять, известно, что по тексту сколь угодно сложной программы , не запуская её в работу, или не имея гипотезу о том, что она делает, трудно понять, что она вычисляет.
Вопрос 21. Классификация автоматов. Автоматы и грамматики.
1) Грамматика типа 0 (произвольная)- автомат МТ. Тезис Поста утверждает, что каждая грамматик типа 0 может быть реализована в виде МТ. Доказательство — если множество конечно то можно построить грамматику из аксиомы которой выводятся все строки множества. Если множество счетное, то должна существовать эффективная процедура (алгоритм), которая распознает строки принадлежащие этому множеству. Понятно что никакое свойство языков порождаемых грамматикой типа 0 не является алгоритмически разрешимым в соответствии с теоремой Райса.
2) Грамматика типа 1 (контекстная) — Машина Майхилла. Задается командами: (qi, aj ? qi|, aj|, lk ) где l k ? N и говорит на сколько позиций смещается лента влево (и только влево) или на одну вправо.
3) Тип 2 — Контекстно-свободная — магазинный автомат, представляющий собой некоторое устройство управление, имеется полу — лента справа и слева и стек. Используется: 1) для распознавания строк принадлежащих некоторой грамматике. По входному каналу поступает исходное слово, в выходной канал поступает результат. 2) Порождение строк принадлежащих некоторому языку (генерация кода). 3) Объединения задача распознавания и порождения для организации процесса компиляции . М=<V,Q,A,P,B,I>, где V- входной алфавит, Q — множество состояний, A — внутренний алфавит стека, P — отображения Q?V (Q?V?A ? Q?A?B), B — выходной алфавит, I- начальная конфигурация
4) Грамматика типа 3 (регулярная грамматика) соответствует конечному автомату. A ? W, a ? V ; A?a ; A?aB — левосторонний вывод, A?Ba — правосторонний вывод.
Вопрос 22. Классификация автоматов. Автоматы и грамматики.
Между грамматиками и автоматами можно установить следующее соответствие.
Грамматика типа 0 соответствует МТ как автомату . Контекстная грамматика (1) — автомат Майхилла (Сеть Петри ) Грамматика типа (2) –магазинный автомат. Граммтика типа (3) – конечный автомат
Автомат типа 0 – или МТ