Материал: Ответы на экзаменационные вопросы по математической логике

28. Самоприменимость МТ. Теорема об алгоритмической неразрешимости проблемы самоприменимости

Как и раньше, кодируем натуральные числа символом 1. Будем рассматривать МТ, алфавит которых содержит символ 1.

МТ называется применимой к начальному слову, если она, начав работать с этим словом на ленте, придёт в заключительное состояние.

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

Пример тьюринговой функциональной схемы самоприменимой машины:

1 00 11

Данная машина работает так: к любому слову, состоящему из символов 1, она прибавляет ещё один символ 1 справа и останавливается.

Очевидный пример несамоприменимой машины — если в правых частях команд не встречается 0 — стоп-состояние. Такая машина неприменима ни к какому слову.

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

Теорема. Проблема самоприменимости алгоритмически неразрешима, то есть не существует МТ, решающей эту проблему в указанном выше смысле.

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

Предположим противное, что такая машина существует (например, в номер самоприменимой машины перерабатывается в 1, а несамоприменимой в 0). Тогда можно построить машину , которая:

1)Применима ко всем кодам номеров несамоприменимых машин (то есть по номеру устанавливает, что машина несамоприменима).

2)Неприменима ко всем кодам номеров самоприменимых машин.

Действительно, машина получается из следующим образом: алфавит сохраняется неизменным, заключительное состояние 0 машины считается не заключительным состоянием машины , а заключительным состоянием считается новое состояние 0′ , причём программа состоит из всех команд и ещё двух команд:

10 → 10 («зацикливание»)

00 → 00′

Очевидно, что удовлетворяет требованиям 1) и 2), так как конфигурация 1

0

машины означает, что установлена самоприменимость исследуемой МТ, а команда 10 → 10 зацикливает программу, что означает, что неприменима к номеру

самоприменимой МТ; в то же время заключительная конфигурация 0 машины

0

устанавливает несамоприменимость МТ, а команда 00 → 00′ означает, что применима к несамоприменимой МТ (не зацикливается).

Итак, если самоприменима (то есть применима к коду своего номера), то она применима и к коду самоприменимой МТ, но тогда требование 2) не удовлетворено; если же несамоприменима (то есть неприменима к коду своего номера), то она неприменима и к коду несамоприменимой МТ, но тогда не выполнено требование 1). Следовательно, мы пришли к противоречию, то есть не существует машины , решающей проблему самоприменимости.

Заметим, что неразрешима именно массовая проблема: не существует единого алгоритма, который решал бы проблему самоприменимости.

Используя результат этой теоремы, можно доказать неразрешимость других алгоритмических проблем. Например, можно доказать следующую теорему.

Теорема. Проблема применимости МТ к начальному слову алгоритмически неразрешима, то есть не существует МТ (а, следовательно, и алгоритма), разрешающей проблему определения по номеру (МТ) и начальному слову , применима ли МТ к .

Иначе говоря, можно ли построить МТ, которая была бы применима ко всем словам вида (МТ)0 (МТ — произвольная машина, 0 — разделитель, — произвольное слово), и в случае, если МТ применима к слову , то заключительная конфигурация

29. Нормальные алгоритмы Маркова. Точное определение алгоритма. Примеры

Будем называть алфавитом всякое непустое конечное множество символов, а сами символы алфавита будем называть буквами.

Слово в алфавите — всякая конечная последовательность букв алфавита . Пустая последовательность букв называется пустым словом и обозначается .

(1 2) 3 = 1(2 3).

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

Алфавит называется расширением алфавита , если . Очевидно, что в этом случае всякое слово в алфавите является также словом в алфавите .

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

Пусть есть слово в алфавите ; говорят, что алгоритм применим к слову , еслисодержится в области определения .

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

Если и — слова в алфавите , то выражение → называется простой формулой подстановки в , а →∙ называется заключительной формулой подстановки в ; при этом предполагается, что символы стрелка «→» и точка «∙» не являются буквами алфавита , а каждое слово и может быть и пустым словом.

Пусть → (∙) обозначает одну из формул подстановки → или →∙ .

Конечный список формул подстановки в алфавите :

1 → (∙) 1 { 2 → (∙) 2

…

→ (∙)

Называется схемой алгоритма и порождает следующий алгоритм в алфавите ,

называемый алгоритмом Маркова или нормальным алгоритмом.

Пусть — слово в алфавите . Здесь может быть одно из двух:

1)Ни одно из слов 1, 2, … , не входит в слово (обозначается: : ).

2)Среди слов 1, 2, … , существуют такие, которые входят в . Пусть — наименьшее целое число из 1 ≤ ≤ такое, что входит в , и — слово, которое получается, если самое левое вхождение слова в слово заменить

словом .

Тот факт, что и находятся в описанном отношении, коротко запишем в виде: : , если → (∙) — простая подстановка;

: ∙ , если → (∙) — заключительная подстановка.

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

пишут : ∙ ).

Положим теперь ( ) = тогда и только тогда, когда либо : ∙ , либо :

и : .

Это и есть точное (строгое) определение алгоритма. Любой алгоритм, если он существует, может быть представлен как нормальный алгоритм Маркова.

Таким образом, работу алгоритма можно описать следующим образом:

Пусть дано слово в алфавите . Находим первую в схеме алгоритма формулу подстановки → (∙) такую, что входит в . Совершаем подстановку слова вместо самого левого вхождения слова в . Пусть 1 — результат такой подстановки. Если →∙ , то работа этой подстановки заканчивается и далее переходим к следующей подстановке, такой, что входит в 1 (то есть к -той подстановке), и так же совершаем подстановку → (∙) , результат которой 2 и так далее. Если же → , то применяем к 1 тот же поиск, который был только что применён к (до тех пор, пока входит в ) и так далее.

Если на конечном этапе будет получено такое слово , что : , то есть ни одно из слов 1, … , не входит в , то работа алгоритма заканчивается, и будет его значением. Если же описанный процесс на конечном этапе не заканчивается, то говорят, что алгоритм неприменим к данному слову .

Примеры.

1.Пусть схема алгоритма: : → , → .

Тогда, если начальное слово , то алгоритм работает так:

→ → → , :

Обратим внимание на то, что → произошло потому, что заключительной подстановки в схеме алгоритма нет. Закончиться алгоритм может, как уже было написано ранее, либо при последней заключительной подстановке : ∙ , либо при простой подстановке : при отсутствии зацикливания ( → , → ).

2.Пусть схема алгоритма: : →∙ , →∙ .

Тогда, если начальное слово , то алгоритм работает так:

3.Пусть схема алгоритма: : → , →∙ .

Тогда, если начальное слово , то алгоритм работает так:

4.Пусть схема алгоритма: : → , → .

Тогда, если начальное слово , то алгоритм работает так:

→ → →

Так как подстановка → — простая, то алгоритм не заканчивается, процесс продолжается бесконечно, значит данный алгоритм неприменим к данному слову.

Пример 1. Пусть есть алфавит { , } . Рассмотрим схему → , → . Определяемый этой схемой нормальный алгоритм перерабатывает всякое слово в алфавите , содержащее хотя бы одно вхождение буквы , в слово, которое получается вычёркиванием в самого левого вхождения буквы .

Если = , то →∙ , где = . Данный алгоритм неприменим к пустым словам, не содержащим буквы , так как простые подстановки → будут перерабатывать эти слова в себя самих, но тогда всегда → , и мы не приходим к заключительной подстановке, то есть процесс будет продолжаться бесконечно.

Если же рассмотреть несколько изменённую схему → , →∙ , то алгоритм применительно к слову = сработает так: : ∙ .