Примеры операций МТ

Замечу, что, как это ни парадоксально, одна из наиболее важных – если не самая важная – в истории computer science статья так никогда и не была переведа на русский язык, и желающему ознакомиться с ней придется читать ее на языке оригинала. Аналогичная ситуация, кстати, сложилась и со статьей Курта Геделя, в которой изложены его фундаментальные результаты о неполноте арифметики.

Идея Тьюринга была великолепной (одним из первых, кстати, это оценил уже упоминавшийся Алонзо Черч, благодаря которому конструкция и получила название «машина Тьюринга»). Тьюринг совершил настоящий научный подвиг – он нашел в себе мужество взглянуть на проблему с иной точки зрения (обращаю внимание читателя на эпиграф к статье). И это привело его к успеху.

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

Существует несколько настоящих из «крови и плоти» моделей машины Тьюринга. Наиболее интересная из них, на мой взгляд, представлена на сайте http://aturingmachine.com. Там же заинтересованный читатель может найти описание механической и электронной частей модели.

Но простота конструкции отнюдь не значила, что машина Тьюринга мало на что пригодна – вот уж нет. Это полноценный компьютер, нисколько не слабее любых самых современных и мощных машин, разве что очень примитивно устроенный. И в этой самой простоте – залог успеха: простота не закрывала саму проблему, а помогала ее решить.

В многочисленных книгах по математической логике, теории рекурсивных функций и информатике машина Тьюринга описана описана не раз и не два. Все эти описания в равной степени эквиваленты, но порой довольно значительно отличаются в технических деталях. Выбрать из них лучшее – задача сложная. Возможно, это был вариант, предложенный Марвином Минским [8], кстати, одним из лауреатов премии Тьюринга. Я тем не менее не буду отклоняться от варианта, предложенного самим Тьюрингом в его статье.

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

В основе кодирования Геделя лежит так называемая основная теорема арифметики: всякое натуральное число может быть единственным (до порядка множителей) образом разложено на произведение простых чисел. Скажем, число 10 единственным образом можно разложить (современный термин – «факторизовать») в виде 2х5; число 20 можно единственным образом разложить как произведение 2 х 2 х 5 или 22 х 5 и т.д.

Посредством этого метода Гедель смог закодировать все арифметические утверждения и вывести путем тонких рассуждений свои теоремы о неполноте.

Я здесь не буду воспроизводить доказательство, данное Тьюрингом, о неразрешимости entscheidungsproblem – мне не хочется создавать иллюзию понимания; само по себе доказательство просто, но «головоломно» (эта характеристика принадлежит М. Минскому).

В действительности доказательство опирается на возможность задания машине Тьюринга описания самой себя. Машина Тьюринга, способная выполнять программы, описывающие ее работу (т.е. программа, получающая саму себя на входе), называется универсальной машиной Тьюринга. Ничего необычного в таком «самоприменении» (от англ. self-referencing) нет – это пример рекурсивной функции, подобной классическим функциям факториала или последовательности Фибоначчи, правда, несколько необычного вида.

Будет куда интереснее и полезнее либо найти и попытаться прочитать статью самого Тьюринга, либо воспользоваться хорошим университетским учебником по теории рекурсивных функций (я рекомендую, помимо упомянутой выше книги М. Минского, следующие: [9-11] и особенно вышедшую совсем недавно научно-популярную книгу [12].

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

Важное открытие

Машина Тьюринга (далее я буду использовать сокращение «МТ») – это воображаемое устройство, состоящее из бесконечной ленты, разделенной на ячейки и головки чтения/записи. В оригинальной МТ ячейка может содержать символы трех типов: 0, 1 и быть пустой (в последнем случае ячейка не содержит ни 0, ни 1, и ее удобно обозначить через «-»).

Замечу, что МТ не налагает ограничений на используемый набор символов: можно применять любые символы, которые программист сочтет нужным, – это существенно упрощает составление программ для МТ (вскоре будет приведен соответствующий пример).

В каждый отдельный момент времени головка находится над одной из ячеек и считывает ее содержимое. В зависимости от содержимого ячейки МТ может выполнить одну из следующих операций: стереть текущее содержимое ячейки (операция «E»), напечатать что-либо в ячейке («P»), сдвинуть головку вдоль ленты на одну ячейку влево («L») или вправо («R»). Полезна и еще одна операция – останов («H»).

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

Следующее состояние – вовсе не обязательно состояние, текстуально следующее за текущим состоянием; оно может располагаться на значительном «удалении» от текущего.

Операций может быть не одна, а несколько (например, стереть символ, напечатать 1, сдвинуть головку влево, что можно записать как «E, P1, L»). Разумеется, проще всего работу МТ продемонстрировать на нескольких примерах, чем я сейчас и займусь.

Пример 1

На пустой ленте напечатать пять единиц и остановиться.

Состояние   Текущий символ   Операция   Следующее состояние
    a              -           P1, R             b
    b              -           P1, R             c
    c              -           P1, R             d
    d              -           P1, R             e
    e              -           P1, H

Легко проверить, что эта программа МТ действительно печатает на пустой ленте последовательность «11111», после чего останавливается.

Пример 2

На пустой ленте напечатать последовательность из 0 и 1.

Состояние   Текущий символ   Операция   Следующее состояние
    a              -           P1, R             b
    b              -           P0, R             a

Эта программа МТ, никогда не останавливаясь, будет печатать последовательность «101010...». Это не должно нас беспокоить, т.к. лента МТ также бесконечна. Главное в этом примере то, что из него видно, как в программе для МТ можно организовать цикл.

Пример 3

На пустой ленте напечатать последовательность из 0 и 1, разделенных пустым символом (это, кстати, самый первый пример из статьи Тьюринга, в котором я только изменил обозначения состояний).

Состояние   Текущий символ   Операция   Следующее состояние
    a              -           P0, R             b
    b              -             R               с
    c              -           P1, R             d
    d              -             R               a

На ленте будет напечатано «0-1-0-1-0-1-0...», и так до бесконечности (я использовал символ «-» для обозначения пробела).

Пример 4

Сложение чисел. На ленте имеются два числа, представленные в единичной форме (т.е. число «3» представляется как последовательность «111»), разделенных одной пустой ячейкой. Записать на ленте последовательность, представляющую собой сумму двух чисел.

Пусть информация на ленте МТ представлена в виде «-111-11111-». По окончании работы программы на ленте должна остаться последовательность «-11111111-». Головка МТ в начале работы считывает самую левую единицу.

Состояние   Текущий символ   Операция   Следующее состояние
    a              1              R              a
    a              -            P1, R            b
    b              1              R              b
    b              -              L              c
    c              1             E, H

Обращаю внимание, что начальных (текстуально в программе – самых левых) состояний может быть сколько угодно. МТ может находиться в состоянии b и считывать символ 1, а может находиться в том же состоянии, но считывать пустой символ. Таким образом, программы МТ носят условный характер: при заданном состоянии и текущем символе требуется выбрать ту или иную операцию.

Программа работает так: первая последовательность из единиц сканируется слева направо до тех пор, пока не будет обнаружена ячейка, содержащая пустой символ. В эту ячейку записывается единица. Теперь общее число единиц на ленте ровно на одну больше, чем надо. Чтобы «скорректировать» сумму к правильному значению, необходимо найти самую правую единицу, стереть ее и остановиться. Упрощенно ход работы МТ выглядит так: «-111-11111-» «-111111111-» «-11111111-», где выделены единица, записанная вместо пустого символа, и «лишняя» единица в конце промежуточной последовательности.

В заключение я хочу предложить читателям несколько упражнений (в порядке возрастания сложности) для развития навыков программирования для МТ.

• Упражнение 1: написать программу, перемножающую два числа, записанных в формате предыдущего примера.
• Упражнение 2: написать программу, вычитающую одно число из другого.

В этом упражнении есть маленький подвох: чему равна разность двух чисел, обозначенных как «a» и «b», если a < b? Ведь для натуральных чисел (т.е. для чисел из ряда 0, 1, 2...) операция вычитания не всюду определена – отрицательных чисел «не предусмотрено». Обычно математики определяют операцию вычитания на натуральных числах так: если a ? b, то разность вычисляется как обычно; если a < b, то разность a и b равна 0 (т.н. «усеченная» разность).

• Упражнение 3: проверка правильности вложения скобок. Имеется строка, состоящая из произвольного количества символов «(» и «)». В строке «(())» скобки сбалансированы, равно как и в последовательности «(()(()))». А вот для строк «()(» и «)()(» скобки не сбалансированы. Написать программу для МТ, которая проверяет баланс скобок.

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

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

Несложно написать программу на любом высокоуровневом языке программирования, которая эмулирует работу МТ. Такой программе можно «поручить» проверку программ для МТ. Много таких программ можно найти в Интернете (правда, не исключено, что для них придется немного поправить исходные тексты программ, приведенных в статье).

• Упражнение 4: подпрограммы. В этом упражнении я предлагаю поразмышлять над тем, как смоделировать на МТ концепцию подпрограмм. Где и как должен сохраняться адрес возврата? Это интересная задача для любителей нестандартных решений.

***

Когда-то выдающийся американский физик-теоретик Ричард Фейнман в своих знаменитых «Фейнмановских лекциях по физике» (правда, по иному поводу) сказал: «...мы сможем продемонстрировать одно из прекрасных свойств... – как много в ней удается вывести из столь малого».

Работа Алана М. Тьюринга по праву может считаться классической иллюстрацией слов Фейнмана. Действительно, кто бы мог предположить, что математическая статья в специализированном журнале по малопонятной и далекой от повседневных проблем тематике, к тому же написанная практически не известным математиком, окажет такое воздействие на нашу цивилизацию. Но не прошло и 20 лет, как компьютеры стали производиться в промышленных масштабах. Поначалу это были огромные многотонные чудовища, пожирающие сотни киловатт электроэнергии и способные обогреть выделявшимся теплом целый квартал. Их программирование было немногим легче, чем программирование МТ. Но очень скоро компьютеры, причем куда более мощные, чем, вероятно, даже Тьюринг мог себе вообразить, уменьшились в размерах до крохотных пластинок и капсул, встраиваемых в автомобили, телевизоры, стиральные машины и космические спутники.

Как бы ни отличались современные компьютеры и в особенности их программное обеспечение от того, что когда-то на прогулках по парку придумал Тьюринг, все они фактически являются потомками великого изобретения – машины Тьюринга.

Материал с сайта http://samag.ru/archive/article/1092