Уточнение понятия алгоритма

В истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.

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

В 1900 году на втором международном математичес­ком конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математи­ческой общественности. Среди них была и следующая 10-ая проблема Гильберта: требуется выработать алго­ритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.

Рассмотрим всевозможные диофантовы уравнения, т.е. уравнения вида Р = 0, где Р является многочленом с целочисленными коэффициентами. Такими будут, например, уравнения

х² + у² - 2хz = 0,

10x⁵ + 7x² + 5 = 0,

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

Так, уравнение х² + у² - 2xz = 0имеет бесконечное множество целочисленных решений, а уравнение

10x⁵ + 7x² + 5 = 0 таких решений не имеет.

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

P_n(x)= a ₀xⁿ+ a ₁x^n-1+ a ₂x^n-2+…+ a _n-1x + a _n = 0

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

1. Найти все делители числа a _n: d₁, d₂,..., d_n.

2. Вычислить Pn(x) Для каждого из делителей числа a _n.

3. Если при некотором i из совокупности 1, 2,..., k
P_n(d_j) = 0, то d_i - корень уравнения. Если при всех i = 1, 2,..., k P_n(d_j)  0, то уравнение не имеет целочис­ленных решений.

Поиски решения десятой проблемы Гильберта привлек­ли внимание многих математиков и длились около 70 лет. Только в 1968 году молодым математиком Ю. Матиясеви чем было доказано, что нет алгоритма, дающего решение поставленной задачи.

Интуитивное определение алгоритма хотя и не строгое, но настолько ясное, что не дает оснований для со­мнений в тех случаях, когда речь идет о найденном алго­ритме решения конкретной задачи.

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

Действительно, в этом случае нужно либо доказать существование алгоритма, либо доказать его отсутствие.

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

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

Во-первых, такое определение должно было правильно отражать сущность интуитивного определения алгоритма.

Во-вторых, оно должно было быть совершенным с точки зрения формальной точности.

И наконец, различные исследователи этой проблемы исходили из разных технических и логических соображе­ний, и вследствие этого было выработано несколько опре­делений алгоритма. Однако со временем выяснилось, что все эти определения равносильны, т.е. определяют одно и то же понятие. Это и есть современное понятие алгоритма.

В подходах к определению понятия алгоритма мож­но выделить три основных направления.

Первое направление связано с уточнением понятия эффективно вычислимой функции. Этим занимались А. Черч, К. Гедель, С. Клини. В результате был выделен класс так называемых частично-рекурсивных функций, имеющих строгое математическое определение. Анализ идей, приведших к этому классу функций, дал им возможность высказать гипотезу о том, что класс эффективно вычислимых функций совпадает с классом частично рекурсивных функций.

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

Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским ма­тематиком А. А. Марковым.