ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

Q A
|

В начале работы на ленту записывается слово , а вся информация о начале работы определится машинным словом

.

В качестве упражнения постройте последовательность машинных слов, начинающуюся словом .

Из сравнения определений НА и МТ видно, что в последний процесс преобразования слов разбит на более мелкие операции – них в каждый такт заменяется не более одной буквы слова. Кроме того, в них есть и другое сильное ограничение – расширение слова может происходить только за счёт приписывания новых символов слева или справа от слова (т.е. в начале его или конце). В связи с этим строить НА для решения задач, как правило проще, чем МТ. Так, задачу удвоения натурального числа можно решить НА со схемой

,

,

.

В нем всего лишь три команды вместо 9 в построенной выше машине, да и число тактов работы по удвоению слова существенно меньше. На первый взгляд может казаться, что и в принципе МТ имеют меньше возможностей по сравнению с НА. Однако А. Тьюрингом и Э. Постом была выдвинута гипотеза (или тезис) о том, что любой алгоритм над алфавитом A эквивалентен относительно A алгоритму, осуществляемому подходящей машиной Тьюринга (соответственно Поста).

Как и тезис Маркова А. А. Нормализации алгоритмов, эта гипотеза не может быть доказана, её можно лишь подкреплять какими-либо разумными доводами. Наиболее важным из них является известная к настоящему времени теорема о том, что всякий НА осуществим на МТ.

ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

Слово алгоритм (или алгорифм) происходит от имени арабского математика (из Хорезма Мохаммеда ибн Мусы Альхваризми (IX в.), из трактата которого Европа в XII в. познакомилась с позиционной системой счисления и с арифметическими действиями над числами в таких системах. В связи с этим и само понятие алгоритма ассоциировалось в начале с искусством счета. Постепенно понятие алгоритма деформировалось и к началу XX в. под алгоритмом стали понимать четко определенную процедуру решения некоторого класса задач. Конечно, приведенное пояснение не может служить определением понятия алгоритма. Однако, таким весьма туманным понятием алгоритма математики довольствовались вплоть до XX в., пока не появилась необходимость в доказательстве отсутствия алгоритмов для решения некоторых классов задач. Дело в том, что к началу XX в. в математике накопилось много задач алгоритмического характера не поддававшихся решению, несмотря на многочисленные усилия математиков. Примером может служить известная 10-я проблема Гильберта сформулированная им в докладе “Математические проблемы”, произнесенном в 1900 году на II Международном конгрессе математиков в Париже. Эта проблема заключалась в нахождении способа, позволяющего за конечное число операций установить, разрешимо ли произвольно заданное алгебраическое уравнение с целыми коэффициентами в целых числах или нет. Наличие таких задач зарождало у математиков идею о доказательстве отсутствия алгоритмов их решения. Результаты об отсутствии алгоритмов решения задач теми или иными ограниченными средствами к тому времени уже были. Например, было известно, что задачи трисекции угла, удвоения куба и т. д. неразрешимы с помощью циркуля и линейки. Однако теперь речь шла об отсутствии алгоритмавообще. Для решения такого рода задач необходим был новый качественный скачок в математике. А именно, нужно было дать точное определение понятия алгоритма, поскольку невозможно доказать отсутствие чего-то туманного и расплывчатого.

Задача определения алгоритма была решена в 30-х годах XX в, в ра­ботах математиков и логиков Гильберта, Гёделя, Чёрча, Клини, Поста и Тьюринга. Было дано несколько разных определений понятия алгорит­ма. При этом Гильберт, Гёдель, Чёрч и Клини подошли к понятию алго­ритма через вычислимые арифметические функции, а Пост и Тьюринг - через сведение алгоритма к элементарным преобразованиям слов в ко­нечных алфавитах.

Второй подход к определению алгоритма был использован в 40-х годах и советским математиком А. А. Марковым (1903—1979). Определенные им алгоритмы получили название нормальных алгоритмов Мар­кова.

Прежде чем дать строгое определение алгоритма, математики проанализировали известные примеры алгоритмов и выделили наиболее общие их свойства. Для выявления этих свойств рассмотрим и мы пов­нимательнее, например, хорошо известный из курса алгебры алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел. В нем предписывается делить с остатком 1-е число на 2-е, затем 2-е на полученный (первый) остаток, затем 1-Й остаток на 2-й оста­ток и т. д. до тех пор, пока не получится остаток, равный нулю. Послед­ний, не равный нулю, остаток и будет искомым наибольшим общим де­лителем. В итоге любая пара натуральных чисел a, b преобразуется в число d, равное их наибольшему общему делителю:

(a, b)= d.

Характерными свойствами алгоритма Евклида являются:

1) массовость—алгоритм может быть применен к любой паре натуральных чисел, причем сама схема работы алгоритма не зависит от ис­ходных данных (в любом случае дели 1-е число на 2-е и т. д.);

2) дискретность-весь алгоритм можно разбить на отдельные элементарные операции (шаги алгоритма), которые могут быть занумеро­ваны натуральными числами в порядкеих выполнения;

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

4) конечная определенность—исходные данные, а также результаты каждого шага алгоритма и ответ записываются в виде конечных после­довательностей символов исходного конечного алфавита.

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

На примере алгоритма Евклида просматриваются не только общие черты алгоритма вообще, но и упомянутые выше два подхода к общему определению алгоритма. А именно, с одной стороны, это вычисление значений некоторой числовой функции двух переменных о. 6.. а с другой—преобразование одной последовательности символов (цифр чисел а и b, разделенных запятой) в другую последовательность (цифр числа d).

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

В каждом из имеющихся в настоящее время определений алгоритма, по существу, описывается некоторый класс алгоритмов и приводится обоснование того, что решение любого класса задач сводится к алгоритму из выделенного класса. Обоснование, как правило, заключается в построении большого числа примеров и в доказательстве замкнутости выделенного класса алгоритмов относительно различного рода комбинаций алгоритмов (композиции, объединения, разветвления и т. п.). Наиболее убедительным доводом в указанном обосновании явилось доказательство равносильности всех имеющихся определений алгоритмов. В итоге к настоящему времени в математическом мире сложилось достаточно единодушное мнение о законности имеющихся определений алгоритма. так что если доказывается отсутствие, скажем, нормального алгоритма для решения какого-либо класса задач, то говорится об отсутствии алгоритма вообще.

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

В заключение отметим, что наличие алгоритмически неразрешимых задач ни в коей мере не противоречит общепризнанному положению диалектического материализма о познаваемости мира. Дело в том, что в теории алгоритмов речь идет об отсутствии общего алгоритма для решения слишком широкого (бесконечного) класса задач, а не какой-либо отдельной задачи.