''Я не знаю, кто я - Тьюринг, которому снится, что он машина,
или машина, которой снится, что она Тьюринг!".

Дао Программирования



     Машина Тьюринга - одна из основных конструкций, которые были предложены для уточнения, или адекватной формализации, понятия алгоритма. Машиной Тьюринга m называется пятёрка (или четвёрка, как на моём сайте, нужно было для лабораторной работы =)))
(Q, T, q0, qz, δ),

где:
   Машина Тьюринга работает на неограниченной с обеих сторон ленте, разделённой на ячейки, одну из которых обозревает головка. В любой момент времени все ячейки, кроме конечного числа, заняты пустыми символами. Конфигурацией машины Тьюринга m называется слово вида αqi, где - α и β непустая часть ленты, qi - текущее состояние управляющего устройства, x - обозреваемый головкой символ.


Рисунок 1 - Машина Тьюринга в состоянии qi ,
 конфигурация αqi.

   За каждый такт работы машины Тьюринга головка считывает обозреваемый символ с ленты и записывает на его место новый, при этом машина переходит в новое состяние qj или остаётся в старом, а головка передвигается на одну позицию влево или вправо, либо остаётся на месте.
   Порядок работы машины Тьюринга обычно записывается в виде таблицы, где в каждый столбец первой строки заносится возможное состяние машины Тьюринга qi Є Q, а в каждую строку первого столбца заносится символ внешнего алфавита x Є T. В других ячейках записываются команды исполняемые машиной Тьюринга в состоянии qi при обозревании символа x (ячейка пуста, если предпологается, что символ x не встречается в состоянии qi). Формат команды задаётся тройкой aKq, где а - символ печатаемый на ленте, К - направление движения головки из {L, R, S}, q - новое состояние машины Тьюринга.

   Рассмотрим программу сложения двух чисел заданных на ленте в унарной системе счисления для машины Тьюринга. Программа принимает 2 числа разделённых символом разделителя ('*'), и записывает результат их сложения на ленте сразу за этими числами отделяя его символом '='. Начальное состояние машины Тьюринга - q0, а головка обозревает первый символ первого числа. Конечное состояние - qz, при этом головка возвращается к исходной позиции. Программа перед своим завершением должна восстановить исходные данные на ленте.


Рисунок 2 - Пример начального состояния машины Тьюринга

Рисунок 3 - Пример конечного состояния машины Тьюринга

    Итак, внешний алфавит для решения данной задачи представляет из себя множество T = {λ, 1, 0, *, =}, а программа выглядит следующим образом:

  q0 q1 q2 q3 q4 q5 = qz
1 0 R q1 1 R q1 1 R q2 1 L q3   1 S qz
0       0 R q0 1 L q4  
* * R q0 * R q1   * L q3 * L q4  
= = L q4 = R q2   = L q3    
λ   = R q2 1 L q3   λ R q5  
Программа 1 - Программа сложения двух чисел в унарной системе для машины Тьюринга

   Как работает данная программа ? Достаточно просто. Она находит очередной символ '1' слогаемых, заменяет его на символ '0' (своеобразная пометка, что этот символ уже обработан) и записывает очередной символ '1' в результат. Затем головка возвращается к началу в поисках символа '0'. Если есть ещё символы '1' до символа '=', то повторяем предыдущий шаг, в противном случае - возвращаем головку в исходное состояние, восстанавливая на ленте входные данные (заменяем '0' на '1').

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

   Для более близкого знакомства с машиной Тьюринга, рекомендую её имитатор Algo2000 Зартидова Радика. На мой взгляд - это лучшая реализация имитатора машины Тьюринга.

[26.12.02]


Текст взят с сайта http://aforge.ibd.lv