Математическая логика и теория алгоритмов. Галуев Г.А. - 49 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 49 из 64
© 2003 Галуев Геннадий Анатольевич
прежнему перерабатывает в слово L, а ко всякой записи самоприменимого алгоритма
неприменим (остановка никогда не наступает). Это приводит к противоречию.
Действительно, если Δ' самоприменим, то он применим к собственной записи в
виде слова, то есть остановка должна наступать. Но по построению алгоритма Δ' это
свидетельствует как раз о том, что Δ' несамоприменим
. Если же Δ' несамоприменим,
то по своему построению, он применим к своей записи, так как он применим к любой
записи неасамоприменимого алгоритма. Но это как раз и означает, что Δ' самоприме-
ним.
Полученное противоречие показывает, что алгоритм Δ' не может быть построен.
Отсюда вытекает, что проблема распознавания самоприменимости алгоритмически
неразрешима.
Таким образом, решая какую-либо задачу, приходится считаться с тем, что ал-
горитм для ее решения может существовать. Поэтому важным является не только по-
строение самого алгоритма, но и доказательство невозможности его построения. Ина-
че говоря существуют такие проблемы, которые нельзя решить с помощью формаль-
ных рассуждений и вычислений. Такие проблемы
требуют творческого мышления, ин-
туиции, предвосхищения и других свойственных пока только человеку качеств.
Нормальные алгоритмы Маркова являются хорошей моделью логических алго-
ритмов. В тоже время можно показать, что любой логический алгоритм можно свести
к вычислительному, то есть любую алгоритмическую проблему можно свести к вычис-
лению некоторой целочисленной функции от целочисленных
значений аргументов.
Действительно, пусть все перерабатываемые алгоритмом М Г условия сведены в по-
следовательность и пронумерованы целыми числами: .,...,,
10 n
AAA множество решений
объединим в последовательность
.,...,,
10 m
BBB
Мы можем теперь сказать, что любой алгоритм, перерабатывающий запись
n
A в
m
B , сводится к вычислению значений числовой функции )(nm
ϕ
=
, в которой (после
перенумерации) мы можем иметь дело только с номерами записей и решений, то есть
алгоритм перерабатывает номер записи условий в номер записи решений. Таким об-
разом, мы имеем уже не логический, а численный алгоритм.
Очевидно, что если есть некоторый алгоритм, решающий исходную задачу, то
есть и алгоритм вычисления
значений соответствующей функции.
Таким образом, возможность построения любого алгоритма сводится к понятию
вычислимости функции. В свою очередь, понятие вычислимости функции можно фор-
мализовать с помощью машин Тьюринга. Рассмотрим более подробно понятие машины
Тьюринга, которое является еще одним уточненным (не интуитивным) понятием алго-
ритма.
Машины Тьюринга.
Машина Тьюринга (МТ) состоит из устройства управления, считывающей голов-
ки и бесконечной ленты.
Устройство управления способно принимать некоторое конечное множество состоя-
ний.
Лента разбита на ячейки, в которые заранее вносятся обрабатываемые данные,
записанные в символах некоторого заданного алфавита (в простейшем случае в каж-
дую ячейку заносится один символ).
Головка считывает данные
из ячейки, которая находится прямо перед ней (та-
кая ячейка называется рабочей) и осуществляется запись на ленту промежуточных
результатов, далее происходит сдвиг ленты вправо или влево (в простейшем случае
на одну ячейку).
Процесс работы МТ состоит в следующем. Устройство управления находится в
одном из состояний, головка обозревает рабочую ячейку и
считывает символ, запи-
санный в ней. Устройство управления анализирует этот символ и выдает команду, в
результате выполнения которой может быть изменено содержимое ячейки, а лента

Страницы