Теорема Клини

Любой граф переходов конечного автомата всегда можно представить в нормализованной форме, в которой только одна начальная вершина только с исходящими ребрами и только одна заключительная вершина только с входящими ребрами.

Над графом переходов, представленным в нормализованной форме, могут быть выполнены две операции редукции — редукция ребра и редукция вершины — с сохранением допускаемого этим графом переходов языка. Каждая операция редукции не меняет языка, распознаваемого графом переходов, но уменьшает либо число ребер, либо число вершин.

Следовательно, каждый автоматный язык является регулярным множеством.
Для каждого регулярного выражения R может быть построен конечный автомат (возможно недетерминированный), распознающий язык, задаваемый R. Определение таких автоматов дадим рекурсивно.

Следовательно, каждое регулярное множество является автоматным языком. Теорема доказана.

Функция F называется вычислимой, если существует машина Тьюринга, которая её вычисляет.

Функция F называется универсальной, если выполняются следующие условия: для каждой вычислимой функции f одной переменной x существует постоянная p, такая что для любого x, F(p,x) = f(x). То есть, F может быть использована для моделирования любой вычислимой функции одной переменной. Нестрого, p представляет «программу» для вычислимой функции f, а F представляет эмулятор, которому на вход поступает программа и он её выполняет. Следует заметить, что для любого фиксированного p функция f(x) = F(p,x) является вычислимой; таким образом, свойство универсальности утверждает, что таким путём могут быть получены все вычислимые функции одной переменной.

?29. Перечислимые языки. Существование перечислимых, не вычислимых языков.

Множество называется (рекурсивно, или эффективно, или алгоритмически) перечислимым, если либо пусто, либо есть область значений некоторой вычислимой функции или, другими словами, если существует алгоритм для последовательного порождения (перечисления) всех его элементов.

Другими словами, перечислимо, если существует такая вычислимая функция , что . Функция называется перечисляющей множество (или для множества ); соответственно алгоритм, вычисляющий , называется перечисляющим или порождающим для .

Существуют три основных эквивалентных определения концепции рекурсивно перечислимого языка.

1. Рекурсивно перечислимый формальный язык, это рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка.

2. Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая перечисляет все корректные строки языка. Заметим, что если язык бесконечен, то можно выбрать алгоритм перечисления, который избегает повторений, так как для строки под номером n можно проверить, была ли она «уже» выдана под номером меньшим n. Если была, то вместо этого использовать вывод под номером n+1 (рекурсивно), снова проверив, является ли он «новым».

3. Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая остановится и примет любую входную строку из языка, но остановится и отвергнет или не остановится вообще для любой входной строки не из языка. Рекурсивные языки требуют останова машины Тьюринга в любом случае.

Все регулярные, контекстно-свободные, контекстно-зависимые и рекурсивные языки являются рекурсивно перечислимыми.

30. Теорема о рекурсии.

Теорема (Клини, о рекурсии):

Пусть — вычислимая функция. Тогда найдётся такая вычислимая , что .

Альтернативная формулировка: Нельзя найти алгоритма, преобразующего программы, который бы по каждой программе давал другую (не эквивалентную ей).

Доказательство:

Начнём с доказательства леммы. Лемма: Пусть на натуральных числах задано отношение эквивалентности . Тогда следующие два утверждения не могут быть выполнены одновременно: 1. Пусть — вычислимая функция. Тогда существует всюду определённое вычислимое — продолжение функции , то есть такая , что и такого, что , выполнено . 2. Найдётся такая всюду определенная вычислимая , что выполнено . Доказательство: Приведем доказательство от противного. Пусть оба утверждения выполнены. Определим функцию так: . Заметим, что никакая всюду вычислимая функция не отличается от всюду. Согласно первому утверждению найдётся всюду определённое вычислимое — продолжение функции . Определим функцию так: , где — функция из второго утверждения. Если , то , то есть . Если , то , так как всюду определена. Значит, всюду отлична от , получили противоречие. Теперь определим отношение так: . Покажем, что для него выполнено первое утверждение леммы. Для заданной определим . Так как — универсальная функция, то найдётся такая всюду определенная вычислимая функция , что . Тогда и будет выполнено . Значит, , то есть — всюду определенное — продолжение . Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного такое, что . ⇐ Предыдущая567891011121314 Дата публикования: 2015-02-03; Прочитано: 1273 | Нарушение авторского права страницы | Мы поможем в написании вашей работы! studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...