Всякий алгоритм может быть задан посредством МТ

 

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

 

Этот тезис не является теоремой, его нельзя доказать, поскольку он представляет собой утверждение о понятии алгоритма, которое не является точным математическим понятием. По существу, тезис Тьюринга — гипотеза, предположение. На чем же основана уверенность в справедливости этого предположения? Главным образом, на опыте. Все известные в математике алгоритмы могут быть заданы посредством МТ. Но содержание тезиса Тьюринга обращено не только в прошлое. Оно содержит и прогноз на будущее: всякий раз, когда в будущем какое-либо предписание будет признано алгоритмом, его можно будет также задать посредством МТ.

 

Итак, машину Тьюринга можно рассматривать как точное математическое понятие алгоритма. Это уточнение было выработано в науке лишь в тридцатые годы нашего века. До этого в математике обходились интуитивным понятием алгоритма. Почему же возникла необходимость в уточнении, математическом определении понятия алгоритма? В математике не было бы необходимости в определении понятия алгоритма, если была бы уверенность в том, что все поставленные математические задачи (и те, которые возникнут в будущем) могут быть алгоритмически решены. До тех пор пока математики занимались построением конкретных алгоритмов, и это им удавалось, они обходились интуитивным понятием алгоритма. Но в первые десятилетия XX века накопилось много классов задач, довольно простых по своей формулировке, для которых алгоритма найти не удавалось. И математикам пришла в голову мысль: а вдруг для того или иного класса задач просто невозможно найти алгоритм? А если его не существует, и они ищут то, чего нет?

Примеры таких классов задач.

1) Мы располагаем алгоритмом, позволяющим по любому уравнению с целыми коэффициентами с одним неизвестным выяснить, имеет ли оно решение в целых числах или нет. А если рассмотреть уравнение с двумя или многими неизвестными?

Существует ли алгоритм, позволяющий по произвольному уравнению с целыми коэффициентами выяснить, имеет оно целочисленное решение или нет?

Эта задача была поставлена еще в 1901 году известным немецким математиком Д. Гильбертом (десятая проблема Гильберта) среди других проблем, которые, по его словам, XIX век передал в наследство XX. Вначале поиски математиков были направлены на нахождение алгоритма, но требуемый алгоритм так и не был найден. И лишь в 1970 году молодой советский математик Ю. В. Матиясевич доказал, что такого алгоритма не существует. Доказать это утверждение, пользуясь только интуитивным понятием алгоритма, было бы невозможно, ибо в таком случае не ясно, несуществование чего нужно доказывать. Имея же математическое уточнение понятия алгоритма, можно доказывать несуществование алгоритма. Несуществование алгоритма понимается, например, как несуществование машины Тьюринга, обладающей нужным свойством.

2) В качестве второго примера рассмотрим проблему слов в ассоциативном исчислении. Ранее рассмотрен ряд конкретных ассоциативных исчислений, для которых существуют алгоритмы, распознающие эквивалентность любых двух слов. Естественно задать вопрос:

Существует ли алгоритм, позволяющий по любому ассоциативному исчислению выяснить, разрешима в нем проблема эквивалентности слов или нет?

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

Определение нормального алгоритма выделяет во множестве всевозможных алгоритмов подмножество алгоритмов специального вида — класс нормальных алгоритмов.

Оказалось, что класс алгоритмов в форме машин Тьюринга и класс нормальных алгоритмов совпадают, эти алгоритмы равносильны.

(Два алгоритма В и С, исходные объекты которых закодированы словами в алфавите А, называются равносильными, если для любого слова Р в алфавите А результат работы этих алгоритмов над словом Р есть одно и то же слово).

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

 

В этом смысле две математические теории алгоритмов: теория нормальных алгоритмов и теория машин Тьюринга, считаются эквивалентными (равносильными).

 

Литература:

1. Макаренков Ю.А., Столяр А.А. Что такое алгоритм? Беседы со старшеклассниками. Мн.: Народна асвета, 1989.

2. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 2-е изд., исправленное. М.: МЦНМО, 2002, 192 с.