Структуры данных и модели вычислений
Исторические сведения
К концу XIX - началу XX века в математике накопилось некоторое количество вычислительных задач, для которых ученые, несмотря на упорные попытки, не могли предложить методов решения. Одной из таких задач является задача о разрешимости диофантова уравнения. В докладе Д.Гильберта, прочитанном на II Международном конгрессе математиков в августе 1900 года, она звучит следующим образом:
"Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах".
Неудачные попытки математиков решить эту и другие подобные задачи привели к мысли о том, что метода их решения может и не существовать. Но, чтобы доказывать подобного рода утверждения, необходимо иметь математическое определение метода, то есть для интуитивных понятий разрешимости и вычислимости необходимо иметь их формальные эквиваленты. Одним из важнейших достижений математики XX века является формирование математических понятий, которые раскрывают сущность интуитивных представлений о том, что такое метод (алгоритм) решения той или иной задачи, что такое вычислимая функция.
Важность этих понятий вытекает не только из общенаучных проблем развития математики, но также из практических задач общества, использующего вычислительную технику в производстве, экономике, инженерных расчетах и нуждающегося в адекватном представлении о возможностях вычислительных автоматов. Приведем краткие исторические сведения о возникновении теории алгоритмов.
В 1932-1935 годах А.Черч и С.К.Клини ввели понятие -определимой функции, которое сыграло важную роль в определении объема интуитивного понятия вычислимой функции.
В 1934 году К.Гедель, на основе идей Дж.Эрбрана, рассмотрел класс функций, названных общерекурсивными, а в 1936 году А.Черч и С.К.Клини доказали, что этот класс совпадает с классом -определимых функций.
В 1936 году А.Тьюринг ввел свое понятие вычислимой функции, а в 1937 году доказал, что оно совпадает с понятием -определимой функции.
