Машина Тьюринга: принципы устройства

share the uri
  • Машина Тьюринга: принципы устройства

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

    • стереть что-то из того, что написано на странице;

    • написать что-то на странице;

    • перевернуть страницу блокнота вперед;

    • перевернуть страницу блокнота назад.

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

    Действия вычислителя связаны с определенным внутренним состоянием, которое после каждого действия может измениться. При этом внутренние состояния не имеют ничего общего с психологией человека-вычислителя, это просто готовность выполнять другие действия, и потому они могут считаться всего лишь некоторыми маркёрами. Например, при умножении чисел столбиком мы умножаем первое число последовательно на десятичные разряды второго числа и записываем это с отступом, а потом суммируем полученные числа. Для того, чтобы перейти к суммированию, вычислитель должен изменить свое внутреннее состояние, сказав себе: «А теперь я буду суммировать».

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

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

    После такого уточнения все возможные элементарные действия человека-вычислителя можно описать четырьмя видами правил. Обозначим множество используемых символов посредством = {s0,…,sn}, где s0 – выделенный пустой символ (аналог пробела в современных текстовых редакторах), а множество возможных внутренних состояний – посредством = {q0,…,qm}. Четыре вида правил следующие:

    • qi,sj → E,qh;

    • qi,s0 → Psk,qh;

    • qi,sj → R,qh;

    • qi,sj → L,qh.

    Смысл первого правила заключается в том, что если вычислитель находится в состоянии qi и текущая клетка ленты содержит символ sj, то он стирает его (заменяет на пустой символ s0), изменяя внутреннее состояние на qh.

    Смысл второго правила заключается в том, что если вычислитель находится в состоянии qi и текущая клетка ленты содержит пустой символ s0, то он печатает символ sk, изменяя внутреннее состояние на qh.

    Смысл третьего правила заключается в том, что если вычислитель находится в состоянии qi и текущая клетка ленты содержит символ sj, то он смещает фокус внимания на одну клетку вправо и изменяет внутреннее состояние на qh. Аналогично для четвертого правила, но в этом случае смещение происходит на оду клетку влево.

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

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

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

    Image1

    Для описания машины достаточно следующих формальных параметров:

    • исходного конечного алфавита символов = {s0,…,sn};

    • конечного набора ярлыков внутренних состояний = {q0,…,qm};

    • четырех действий: стереть (E), напечатать (P), перейти к правой ячейке (R) и перейти к левой ячейке (L);

    • конечного набора правил;

    • состояния ленты – конечного набора ее ячеек с написанными в них символами.

    Вычисление начинается с того, что в начальном состоянии q0 машина сканирует самую левую ячейку с данными, записанными на ленте. Если данных нет, а такое возможно, то вычисление начинается со сканирования выделенной пустой ячейки. Вычисление заканчивается, когда для текущего внутреннего состояния машины qi и сканируемого в текущей ячейке символа sj нет ни одного правила, левая часть которого имела бы вид qi,sj  Результатом вычисления является содержимое ячеек ленты после остановки машины. Таким образом, мы получаем простое и в то же время строгое математическое уточнение понятия вычисления.

    Приведем три простых примера машин Тьюринга.

    Пример 1.

    • Алфавит символов: S={s0,0}.

    • Внутренние состояния: Q={q0}.

    • Правила:

      • q0,s0 → P0,q0

    Эта машина, в начальном состоянии ленты которой все ячейки пусты, напечатает символ “0” и остановится.

    Если к набору ее правил добавить еще одно “q0,0  R,q0”, то она, никогда не останавливаясь, будет печатать бесконечную последовательность символов “0”.

    Пример 2.

    • Алфавит символов: S={s0, 0, 1}.

    • Внутренние состояния: Q={q0, q1}.

    • Правила:

      • q0,s→ P0,q0

      • q0,0 → R,q1

      • q1,s→ P1,q1

    Эта машина, в начальном состоянии ленты которой все ячейки пусты, напечатает в двух последовательных ячейках символы “0” и “1” и остановится.

    Если к набору ее правил добавить еще одно “q1,1  R,q0”, то она, никогда не останавливаясь, будет печатать бесконечную последовательность символов “0” и “1”.

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

    Для простоты число n на входе вычисления будем представлять с помощью n+1 символов “1”, записанных последовательно в соседних ячейках. Если число n равно 0, то оно записывается одним символом “1”.

    Результат вычисления функции fM определим следующим образом:

    fM(n)={числосимволов“1”наленте,есливычислениезавершаетсянеопределено,есливычислениенезавершается}

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

    Пример 3.

    • Алфавит символов: S={s0, 1}.

    • Внутренние состояния: Q={q0, q1}.

    • Правила:

      • q0,1 → R,q0

    Если в начальном состоянии ленты этой машины записаны подряд n символов “1”, то она последовательно проходит через них, доходит до первой пустой ячейки и останавливается. В соответствии с нашим соглашением о функциях это будет означать, что данная машина M вычисляет функцию fM(n)=n+1.

    Если к набору правил добавить еще одно “q0,s P1,q1”, то машина последовательно проходит через все ячейки с “1”, доходит до первой пустой ячейки, печатает в ней символ “1” и останавливается. В соответствии с нашим соглашением о функциях это будет означать, что машина M вычисляет функцию fM(n)=n+2.

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

  • Bibliography

  • Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.
  • Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.
  • Клини С.К. Введение в метаматематику. М., 1957.
  • Мендельсон Э. Введение в математическую логику. М., 1976.
  • Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. М., 1972.