§ 12.5. Сведение любого алгоритма к численному алгоритму. Гёделизация

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

Уточняя понятие алгоритма, мы ввели в рассмотрение нормальный алгоритм Маркова. Эта форма алгоритма удобна для специалиста логика. Для тех же специалистов, которые имеют дело преимущественно с вычислительными машинами, безусловно важнее иметь разработанный стандартный аппарат, более близкий к естественной форме численных алгоритмов.

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

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

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

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

Совершенно аналогично записи возможных решений также включим в занумерованную последовательность

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

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

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

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

Приведем теперь один широко применяющийся метод нумерации — метод Гёделя.

Рассмотрим запись некоторого числа в форме

где и вообще простое число.

Из этой записи видно (в силу теоремы о единственности разложения любого числа на простые множители), что каждому числу однозначно соответствует набор и, наоборот, каждому набору однозначно соответствует число .

Например, если , имеем

С помощью этого способа мы можем нумеровать теперь любые упорядоченные последовательности, состоящие из чисел. Рассмотрим несколько примеров.

1) Каждой паре чисел и для которой мы ищем ее наибольший общий делитель может быть поставлен в соответствие гёделевский номер этой пары

Алгоритм Евклида сведется тогда к вычислению функции .

2) Требуется найти символ, расположенный на месте чисто периодической последовательности, состоящей из бесконечно повторяющейся последовательности чисел . Условию задачи можно поставить в соответствие гёделевский номер

Алгоритм распознавания числа, стоящего на месте, сведется тогда к вычислению значений функции

причем q может принимать лишь значения из множества

3) Уравнению степени, записанному в общем виде — буквы, но не конкретные числа)

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

При уравнение имеет вид

Его решение выражается через коэффициенты так

Перепишем (12.2) в виде строки

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

Наличие среди этих символов символа 1 и символа сложения позволяет записать с помощью этих символов любое число в виде . Припишем этим символам числа:

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

соответствует набор чисел

Набору чисел, как мы знаем, может быть поставлен в соответствие его гёделевский номер, равный

Обратно, по заданному гёделевскому номеру всегда можно восстановить набор чисел, затем каждое число, заменить на тот символ, который ему приписан, и таким образом по гёделевскому номеру будет восстановлена запись любой формулы.

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

4) Пусть требуется перенумеровать все слова в некотором алфавите А. Это легко сделать, поставив в соответствие каждой букве алфавита какое-либо число. Тогда каждому слову в алфавите А будет соответствовать последовательность чисел. Проводя затем обычным способом гёделизацию, получим гёделевский номер этой последовательности. Разумеется, гёделевский номер слова зависит от выбранной системы соответствий букв и чисел. Теперь легко пронумеровать все последовательности слов (например, все дедуктивные цепочки). Действительно, последовательности самих слов однозначно может быть поставлена в соответствие последовательность гёделевских номеров этих слов; проводя гёделизацию вторично, мы можем определить гёделевский номер самой последовательности гёделевских номеров отдельных слов.

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

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