Теория алгоритмов. Распознающие машины Тьюринга.

Алгоритм - это точное предписание о выполнении в некотором порядке системы операций, определяющих процесс перехода от исходных данных к искомому результату для решения всех задач некоторого данного типа. Это неформальное определение алгоритма, известное еще со времен Аль Хорезми (IX век). Предписание считается алгоритмом, если оно обладает следующими свойствами:

1. определенностью, то есть общепонятностью и точностью, не оставляющими место произволу;
   
2. массовостью, то есть возможностью исходить из меняющихся в известных пределах значений исходных данных;
   
3. результативностью, то есть направленностью на получение искомого результата;
   
4. элементарностью шагов, на который разбивается алгоритм.
   

Перечисленных свойств вполне достаточно, чтобы можно было определить, является ли данное конкретное предписание алгоритмом или нет. Совершенно очевидно, что хорошо известное предписание: "Пойди туда, не знаю куда, принеси то, не знаю что"- алгоритмом не является. Удовлетворительным доказательством существования алгоритма считается фактическое описание процесса решения какой-либо задачи. Однако для некоторых известных проблем (например, для проблемы установления общезначимости формул логики предикатов) не удалось найти разрешающего алгоритма. Безуспешные попытки найти такие алгоритмы привели к предположению, что их не существует. Кроме того математики стремились создавать более общие алгоритмы, которые могли решать большие классы задач. Возник вопрос: "А нельзя ли создать Всеобщий Алгоритм, который решал бы любую математическую задачу аксиоматической теории?". Известный математик Г.В.Лейбниц (1646-1716) считал, что такой алгоритм будет найден. Таким образом, возникла необходимость рассматривать алгоритм как математический объект, что невозможно, так как нет формального определения алгоритма. Так в начале 30-х годов XX века разные математики предложили несколько понятий формального алгоритма: нормальный алгоритм Маркова; Клини и Гедель определили формальный алгоритм через рекурсивную функцию; в 1937 году Тьюринг дал формальное определение через понятие вычислительной машины. Оказалось что все эти понятия эквивалентны. В 1936 году американский ученый Черч формально доказал, что Всеобщего Алгоритма не существует. Основная гипотеза теории алгоритмов (для машин Тьюринга): любой алгоритм в неформальном смысле может быть реализован на некоторой машине Тьюринга. Эту гипотезу невозможно доказать, потому что она оперирует неформальным понятием алгоритма. Однако обоснование гипотезы есть: все алгоритмы придуманные в течение столетий могут быть реализованы на машине Тьюринга; эквивалентность всех формальных определений алгоритма неслучайна и говорит в пользу гипотезы. Чтобы опровергнуть основную гипотезу необходимо придумать такой алгоритм, который невозможно было бы реализовать на машине Тьюринга, пока такого алгоритма нет. В силу этой гипотезы: алгоритм в формальном смысле - есть машина Тьюринга. Машина Тьюринга - это математическая модель идеализированного вычислительного устройства. Она имеет

1. ленту, разбитую на конечное число ячеек, в каждой ячейке ленты в определенный момент времени записан один из символов а0,а1,а2,...,аN. Совокупность этих символов называется входным алфавитом;
   
2. конечное управление, которое может находиться в каждый момент времени в каком-то одном состоянии q0, q1, q2,...,qM;
   
3. управляющую головку, которая может перемещаться вдоль ленты, считывать или записывать символы.
   

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

T= {K,S, Г, d, q0, F}

• K - конечное множество внутренних состояний;
  
• S - входной алфавит;
  
• Г - ленточный алфавит: S: Г-{$}, $-пробел;
  
• d - команды, частичное отображение d: KхГ->Kx (Г-{$})x{L,R}, где L,R -движение головки влево и вправо;
  
• q0- начальное состояние, с него машина начинает обработку, q0cK;
  
• F - множество конечных состояний, в которых машина переходит в представляющее состояние.
  

Здесь можно получить полную информацию в формате PDF, а также скачать программу с исходными текстами