В истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.
    Одним из ярких примеров такого случая является история решения десятой проблемы Д. Гильберта.
    В 1900 году на втором международном математическом конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математической общественности. Среди них была и следующая 10-я проблема Гильберта: требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.
    Рассмотрим всевозможные диофантовы уравнения, то есть уравнения вида \(P=0\), где \(P\) является многочленом с целочисленными коэффициентами. Такими будут, например, уравнения $$x^{2} + y^{2}- 2xz=0,$$ $$10x^{5} +7 x^{2} +5=0,$$
из которых первое с тремя неизвестными, а второе с одним неизвестным. В общем случае рассматривают уравнения с любым числом неизвестных. Такие уравнения могут иметь целочисленные решения, а могут и не иметь.
    Так, уравнения \( x^{2} + y^{2}- 2xz=0 \) имеет бесконечное множество целочисленных решений, а уравнение \( 10x^{5} +7 x^{2} +5=0 \) таких решений не имеет.
    Для частного случая диофантова уравнения с одним неизвестным давно известен алгоритм, позволяющий найти все целочисленные решения. Установлено, что если уравнение $$P_{n} (x) = a_{0}x^{n}+ a_{1}x^{n-1}+...+ a_{n-1}x+a_{n}=0$$
с целочисленными коэффициентами имеет целый корень, то он обязательно является делителем \(a_{n}\). В связи с этим можно предложить такой алгоритм:
    1) Найти все делители числа \(a_{n}: d_{1}, d_{2},...,d_{n}\).
    2) Вычислить \(P_{n} (x)\) для каждого из делителей числа \(a_{n}\).
    3) Если при некотором \(i\) из совокупности \(1,2,...,k\) \(P_{n}(d_{i}) =0\), то \(d_{i}\) – корень уравнения. Если при всех \(i=1,2,...,k\) \(P_{n}(d_{i})\neq 0\), то уравнение не имеет целочисленных решений.
    Поиски решения десятой проблемы Гильберта привлекли внимание многих математиков и длились около 70 лет. И только в 1968 году молодым математиком Ю. Матиясевичем было доказано, что нет алгоритма, дающего решение поставленной задачи.
    Интуитивное определение алгоритма хотя и не строгое, но настолько ясное, что не дает оснований для coмнений в тех случаях, когда речь идет о найденном алгоритме решения конкретной задачи.
    Положение существенно меняется, коrда возникает алгоритмическая проблема, решение которой не найдено, и требуется установить, имеет ли она решение.
    Действительно, в этом случае нужно либо доказать существование алгоритма, либо доказать eго отсутствие.
    В первом случае достаточно дать описание фактического процесса, решающего задачу. В этом случае достаточно интуитивного понятия алгоритма, чтобы удостоверится в том, что описанный процесс есть алгоритм.
    Во втором случае нужно доказать несуществование алгоритма, а для этого нужно точно знать, что такое алгоритм. Между тем для общего понятия алгоритма точного определения до тридцатых годов ХХ века не было, и по-этому выработка такого определения стала одной из важных задач современной математики. При формулировке этого определения пришлось преодолеть многие трудности.
    Во-первых, такое определение должно было правильно отражать сущность интуитивного определения алгоритма.
    Во-вторых, оно должно было быть совершенным с точки зрения формальной точности.
    И наконец, различные исследователи этой проблемы исходили из разных технических и логических соображений, и вследствие этого было выработано несколько определений алгоритма. Однако со временем выяснилось, что все эти определения равносильны, то есть определяют одно и то же понятие. Это и есть современное понятие алгоритма.
    В подходах к определению понятия алгоритма можно выделить три основных на-правления.
    Первое направление связано с уточнением понятия эффективно вычислимой функции. Этим занимались А. Черч, К. Гедель, С. Клини. В результате был выделен класс так называемых частично-рекурсивных функций, имеющих строгое математическое определение. Анализ идей, приведших к этому классу функций, дал им возможность высказать гипотезу о том, что класс эффективно вычислимых функций совпадает с классом частично рекурсивных функций.
    Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил самую общую и вместе с тем самую простую концепцию вычислительной машины. Ее описание было дано Тьюрингом в 1937 году. При этом Тьюринг исходил лишь из общей идеи работы машины как работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием.
    Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. В рамках этого направления алгоритм рассматривается как конечный набор правил подстановок цепочек символов.

---