Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

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

Из школьного курса известно, как осуществляется бисекция угла при помощи циркуля и линейки. Еще у древ­ них греков возникла аналогичная задача о трисекции угла при помощи циркуля и линейки. Однако было доказано, что трисекцию произвольного угла невозможно осущест­ вить этими средствами.

Из школьного курса также известно, что корни квадрат­ ного уравнения выражаются через его коэффициенты при помощи формулы, в которой фигурируют знаки арифме­ тических операций и знак радикала (второй степени). Для уравнений третьей и четвертой степеней также установлены формулы в радикалах, которые, правда, значительно слож­ нее, причем в них встречаются «многоэтажные» радикалы. Однако поиски подобных формул в радикалах для уравне-' ний степени выше четвертой, продолжавшиеся до начала X I X века, оказались безуспешными, пока, наконец, был установлен следующий замечательный результат.

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

В обоих этих случаях доказательства невозможности -сами оказались возможными, поскольку имелись два точных определения, дающих ответы на вопросы: «что значит пост­ роение с помощью циркуля и линейки?» и «что значит реше­ ние уравнения в радикалах?». Заметим, кстати, что в этих

66

ритма для решения уравнений) и алгоритма трисекции лю­ бого угла при помощи циркуля и линейки (а не вообще алго­ ритма трисекции). Для о б щ е г о понятия алгоритм мы точного определения до недавнего времени не имели, и по­ этому выработка такого определения стала одной из важных задач современной математики. Весьма важно подчерк­ нуть, что выработку определения понятия алгоритм (как, впрочем, и всякого другого математического определения) Нельзя рассматривать как произвольное соглашение мате­ матиков об одинаковом понимании термина алгоритм. При формулировке этого определения пришлось преодолеть трудности, заключающиеся в том, что предлагаемое опре­ деление должно правильно отражать сущность того поня­ тия, которое фактически уже имелось, хотя и в расплыв­ чатом виде, и которое иллюстрировалось нами на многочис­ ленных примерах. С этой целью, начиная с тридцатых го­ дов XX века, был предпринят ряд исследований для выяв­ ления всех тех средств, которые фактически привлекаются для построения алгоритмов. Задача состояла в том, чтобы на этой основе дать определение понятия алгоритм, ко­ торое было бы совершенным не только с точки зрения фор­ мальной точности, но, главное, и с точки зрения фактиче­ ского соответствия сущности определяемого понятия. При этом различные исследователи исходили из разных техни­ ческих и логических соображений, и вследствие этого было выработано несколько определений понятия алгоритм. Однако впоследствии выяснилось, что все эти определения равносильны между собой и, следовательно, определяют одно и то же понятие; это и есть современное точное поня­ тие алгоритм.

То обстоятельство, что все способы уточнения понятия алгоритм, несмотря на свое различие и многообразие, всегда приводили и приводят по существу к одному и то­ му же результату, имеет большое познавательное значение; оно свидетельствует как раз об удачности выработанного определения.

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

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

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

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

§ 8. МАШИНА ТЬЮРИНГА

Отличительные особенности машины Тьюринга по сравнению с электронными машинами, описанными в § 5, 6, заключаются в следующем:

1. В машине Тьюринга расчленение процесса на про­ стые элементарные операции доведено в известном смысле до предельной возможности. Например, операция сложения, фигурирующая в электронной машине как единичная эле­ ментарная операция, здесь сама расчленяется на цепочку еще более простых операций.

Разумеется, это значительно удлиняет процесс, реали­ зуемый в машине Тьюринга, но вместе с тем логическая структура процесса сильно упрощается и приобретает весь­ ма удобный для теоретических исследований стандартный вид.

2. В машине Тьюринга часть памяти*' изображается в виде неограниченной с обеих сторон ленты, разбитой на

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

Такая идеализация оправдывается ранее уже отмечав­ шейся связью между понятием алгоритма и понятием ма­ шины с потенциально неограниченной памятью.

8.1. Определение машины Тьюринга. Перейдем к по­ дробному описанию машины Тьюринга.

*) А именно, так называемая внешняя память.

68

1. Машина располагает конечным числом знаков (сим­

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

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

вольным образом по ячейкам. Однако в зависимости от того, какая была подана начальная информация %, воз­ можны два случая:

а) после конечного числа тактов машина останавливает­ ся, подавая сигнал об остановке; при этом на ленте оказы­ вается изображенной некоторая информация 25. В таком случае говорят, что машина применима к начальной ин­

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

69