DiskretPDF

28. Конфигурации и вычисления машин Тьюринга. Универсальная вычислимая функция. Теорема Клини о нормальной форме.

Конфигурация машины Тьюринга есть кортеж

Из конфигурации непосредственно выводится конфигурация , если .

Из конфигурации непосредственно выводится конфигурация , если .

Из конфигурации непосредственно выводится

конфигурация , если .

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

Конфигурация выводима из конфигурации , если существует

вывод . Число называется при этом длиной вывода. Все обозначения, касающиеся выводимости на множестве конфигураций машин Тьюринга,

остаются такими же, как в случае конечных и магазинных автоматов.

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

соглашению, любая цепочка из множества (для

фиксированного ) отождествляется с цепочкой , т.е. можно отбрасывать любое число пробелов в конце слова.

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

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

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

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

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

рекурсивно.

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

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

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

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

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

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