2. Определение машины Тьюринга

Алгоритм является точным математическим понятием. В качестве формальной модели алгоритма исторически первой была модель машины, предложенная англичанином Аланом Тьюрингом в 40-х годах 20-го века.

Машина Тьюринга представляет собой устройство, содержащее пишущую ленту бесконечной длины. В каждой ячейке может быть записан один и только один символ из входного алфавита машины Тьюринга. Как правило, для простейших задач рассматривают внешний алфавит, состоящий из трех символов: 0, 1, .  - пустой символ, обозначающий, что содержится в ячейке не 0, не 1. «Слово» - последовательность непустых символов, ограниченная слева и справа символом . В начальный момент на ленту записывается какое-то слово. Обычно это слово представляет собой описание некоторой задачи, на которых специализируется данная машина Тьюринга. Кроме ленты, у машины имеется читающая-пишущая головка, которая позволяется считать символ из ячейки или записать в ячейку, непосредственно находящуюся под головкой, какой-то один символ. Машина Тьюринга работает по тактам. Такты машины Тьюринга никак не привязываются к единицам времени, например, секундам. Но! именно в тактах измеряется “время”, затрачиваемое машиной Тьюринга на то, чтобы выполнить обработку входного слова. Разумно и сложность задачи связывать с числом тактов, которую необходимо затратить на Машине Тьюринга для ее решения.

Машина Тьюринга работает по определенным правилам. По сути также правила однотипны и сводятся к следующему:

1. считывает символ в текущей ячейки;

2. по текущему состоянию МТ считывает символы. Определить новое состояние, которое перейдет МТ;

3. записать в ячейку новый символ или оставить предыдущий;

4. сдвинуть ленту на одну ячейку вправо или влево, или остаться в этом же положении и перейти к шагу 1.

3. Тезис Черча-Тьюринга

Тезис Черча утверждает, что класс частично-рекурсивных функций и класс частично-вычислимых функций суть один и тот же класс. Оба данных подхода, а также другие подходы ( Марков, Пост ) привели к одному и тому же классу алгоритмически вычислимых функций и подтвердили целесообразность использования тезиса Черча. Таким образом, сформировался круг понятий теории алгоритмов, важнейшими из которых являются вычислимая функция, рекурсивность (частичная рекурсивность), рекурсивная перечислимость, рекурсивная сводимость, алгоритмическая и вычислительная сложность и др.

На этом фундаменте были получены важные теоретические результаты. Сначала К.Гедель опроверг идею Гильберта, доказав существование в арифметике целых чисел теорем, которые выразимы средствами теории, но не доказуемы и не опровержимы в ней. Затем А.Черч получил аналогичный результат для логики первого порядка. Новиковым П.С. в 1952 году было получено решение классической проблемы тождества для конечно-определенных групп, сформулированной Деном в 1912 году. Знаменитая десятая проблема Гильберта, сформулированная им в 1900 году (о разрешимости диофантова уравнения) была отрицательно решена в 1970 году советским математиком Мятиясевичем Ю.В.

Важнейшими задачами теории алгоритмов являются следующие:

• доказательство алгоритмической разрешимости/неразрешимости проблемы;

• построение эффективного алгоритма или доказательство, что такого алгоритма нет;

• анализ сложности алгоритма;

• разработка языков спецификации алгоритмов и задач;

• проблема построения сведения одних задач к другим; и др.

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

Начала складываться так называемая метрическая теория алгоритмов, основным содержанием которой является классификация задач по классам сложности. Классы: не описываемые, неразрешимые, классы сложности, P – есть эф. алгоритм, NP – нет эффективного алгоритма, экспоненциальные. В итоге сами алгоритмы стали объектом точного исследования, как и те объекты, для работы с которыми они предназначены. Важно отыскание как верхних, так и нижних, и средних оценок сложности вычислений. Важным в практическом плане результатом было построение Л.Г.Хачияном полиномиального по сложности алгоритма для решения задачи линейного программирования, поскольку было показано, что симплексный алгоритм имеет в худшем случае экспоненциальную оценку вычислительной сложности, хотя в среднем ведет себя хорошо. Разработанный Хачияном метод эллипсоидов был развит и для решения задач так называемого выпуклого программирования. С иных позиций полиномиальный алгоритм для задачи линейного программирования разработал американский ученый индийского происхождения Н.Кармаркар.

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