Машина Тьюринга: описание и примеры машин Тьюринга. Программа для машины тьюринга Определение машины тьюринга

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

Машина Тьюринга представляет собой абстрактную вычислительную машину, состоящую из управления с конечным числом состояний и бесконечной ленты, разделенной на ячейки, в каждой из которых хранится один ленточный символ, и одна из ячеек является текущей позицией ленточной головки. Формальная запись машины Тьюринга - это упорядоченный набор M = (X, Q, q 0 , F, I), где

X – внешний алфавит символов (букв на ленте), включающий символ L;

Q – конечный алфавит внутренних состояний;

q 0 – инициальное состояние (начало работы), q 0 Î Q;

F– множество заключительных состояний, FÌ Q;

I - множество инструкций, или машинных команд, каждая из которых принадлежит множеству (Q \ F) ´ X ´ {®} ´ Q ´ X ´ {R,L,S}.

Переходы осуществляются на основе текущего состояния и обозреваемого считывающей головкой символа к следующему состоянию, переписыванию символа и сдвигу головки (вправо R, влево L, на месте S).

Можно определить функцию переходов

d: (Q \ F) ´ X* ® Q ´ X* ´ {R,L,S}, где X* -слова в алфавите X.

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

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

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

В качестве примера рассмотрим работу детерминированной машины Тьюринга, вычисляющей функцию ïm - nï. Упорядоченную пару натуральных чисел (m,n) представляем как слово 0 m 10 n в алфавите X \ {L} = {0,1}, ячейки слева и справа от которого содержат символ L.

Q 0 0 ® LRq 1 Состояния Символ

Q 1 0 ® 0Rq 1 0 1 L

q 1 1 ® 1Rq 2 q 0 LRq 1 1Sq 5 0Sq 5

q 2 0 ® 1Lq 3 q 1 0Rq 1 1Rq 2 ¾

q 2 1 ® 1Rq 2 q 2 1Lq 3 1Rq 2 LLq 4

q 3 1 ® 1Lq 3 q 3 0Lq 3 1Lq 3 LRq 0

q 3 0 ® 0Lq 3 q 4 0Lq 4 LLq 4 0Sq 5

q 3 L ® LRq 0 q 5 ¾ LRq 5 ¾

q 2 L ® LLq 4 *

q 4 1 ® LLq 4 Таблица 1. Программа вычисления функции ôm - nô,

q 4 0 ® 0Lq 4 где функция переходов задается таблицей

q 0 1 ® 1Sq 5 *

Машина Тьюринга M допускает (отвергает) слово wÎ X * , если она останавливается на нем, придя в допускающее (заключительное) состояние. Машина допускает язык LÍ X * , если она допускает все слова языка L. Машина M распознает язык LÍ X * , если она допускает все слова из L и останавливается на словах из X * \ L, не находясь в заключитель ном состоянии. Языки, допускаемые машиной Тьюринга, назовем рекурсивно перечислимым.

Язык L допускается (распознается) за полиномиальное время , если существует машина M, которая допускает (распознает) язык L, причем всякое слово wÎ L допускается (распознается) за время O(n k), где n – длина слова w, а k – не зависящее от w число.

Теперь можно определить класс P, как множество языков LÍ {0,1} * , распознаваемых за полиномиальное время.

Теорема. Класс P есть множество языков, допускаемых за полиномиальное время.

Доказательство. В одну сторону тривиально, если машина M распознает язык L, то она и допускает язык L. Обратно, пусть язык L допускается машиной M за время O(n k), т.е. существует константа c, что любое слово из L длины n допускается не более, чем за T = c×n k шагов. С другой стороны, слова, не принадлежащие L, не допускаются ни за какое время. Построим машину M * , которая на слове w моделирует не более Т = c×n k шагов машины M и останавливается, выдавая 1, если M(w)=1, в противном случае - останавливается, сделав Т = c×n k шагов, выдавая на выход 0. Таким образом, машина M * распознает язык L и сложностной класс P можно рассматривать, как множество языков, допускаемых за полиномиальное время.

Многоленточная машина Тьюринга.

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

За один переход осуществляются следующие действия:

Управление переходит в новое состояние,

На каждой ленте записывается новый (или тот же) символ;

Считывающие головки каждой из лент независимо сдвигаются на одну ячейку (R,L,S).

Языки, допускаемые одноленточными машинами Тьюринга, рекурсивно перечислимы. Допустимы ли многоленточными машинами не рекурсивно перечислимые языки? Ответ в следующей теореме.

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

Доказательство. Одноленточную машину Тьюринга можно представить, как многодорожечную , задавая ее аргументы в виде кортежей. При этом одна дорожка хранит данные, а другая отметку. Смоделируем k - ленточную машину M как многодорожечную машину N, содержащую 2k дорожек, где каждая вторая содержит маркер, указывающий позицию головки соответствующей ленты. Машина N должна посетить каждый из маркеров головок k лент и изменить соответствующим образом символ, представляющий соответствующую ленту, перемещая маркер в том направлении, как это происходило на соответствующей ленте. Наконец, N изменяет состояние М, записанное в конечном управлении N. В качестве допускающих состояний N выбираются все те состояния, в которых запоминалось допускающее состояние M. Таким образом, машина M и N одновременно допускают язык L. Но все языки, допускаемые одноленточной машиной N, рекурсивно перечислимы, поэтому рекурсивно перечислимы все языки, допускаемые многоленточной машиной M.

Теорема. Время, необходимое одноленточной машине N для имитации n переходов k-ленточной машины M, есть O(n 2).

Доказательство. После n переходов машины M маркеры головок разделены не более, чем 2n клетками, так что и машине N надо сдвинуться не более, чем на 2n клеток вправо, чтобы найти все маркеры головок. Теперь ей надо совершить проход влево, изменяя содержимое M лент и сдвигая головочные маркеры, что потребует не более 2n сдвигов влево плюс не более 2k переходов для изменения направления движения и записи маркера в клетку. Таким образом, число переходов N для имитации одного из переходов машины M не более 4n+2k, т.е. O(n). Для n переходов требуется времени в n раз больше, т.е. O(n 2).

Различие во времени вычисления на машинах с разным числом лент сохраняет полиномиальную сложность и для одноленточной машины ограничено с×T(n) 2 , а емкость - с×S(n) (для входа длины n), где T(n), S(n) – параметры k-ленточных машин. Зависимость между емкостью и временем для k-ленточных машин линейная: S £ kT; для входа w длины n

Недетерминированные машины Тьюринга.

По причинам, которые вскоре будут понятны, недетерминированные машины Тьюринга являются ключевым понятием в теории NP-полных задач. Недетерминированная машина Тьюринга отличается от обычной (детерминированной) машины Тьюринга тем, что может иметь более одного перехода от текущей конфигурации к следующей. Недетерминированная машина допускает слово w, если существует хотя бы одна цепочка конфигураций, ведущая от начальной конфигурации в заключительную. Существование других последовательностей конфигураций, не ведущих в заключительное (допускающее) состояние не имеет значение. Работу недетерминированной машины на входе w можно представить в виде дерева, где каждый путь из корня w в лист представляет некоторую последовательность возможных шагов машины. Если s w кратчайшая последовательность возможных шагов работы машины, которая оканчивается допускающей конфигурацией, то ½s w ½ есть время, затраченное машиной на обработку входа w. Если на входе w никакая последовательность не приводит к допускающей конфигурации, то время, затраченное на обработку w не определено. Считается, что недетерминированная машина Тьюринга на входе w параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего состояния или окажется, что ее программа не применима к полученной конфигурации.

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

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

Обозначим через L(M) множество всех слов wÎX*, допускаемых машиной M, L(M) называют языком машины M.

Теорема. Если M недетерминированная машина с полиномиальной временной сложностью T(n), то существует детерминированная машина M ’ , с L(M ’ ) = L(M) и временной сложностью O(c T(n)).

Доказательство. Доказательство основывается на том, что для любой недетерминированной машины Тьюринга M строится детерминированная машина M ’ , которая исследует последовательности конфигураций (пути в дереве недетерминированной машины) и если находит хотя бы одну с допускаемым состоянием, то сама переходит в допускаемое состояние. Обследованные конфигурации помещаются в очередь, длины k (k=1,2…) Построим детерминированную многоленточную машину M ’ , моделирующую недетерминированную машину M. Первая лента машины M ’ хранит последовательность конфигураций машины M и метку на текущее состояние последней. Записи слева от метки предполагаются исследованными и их в дальнейшем игнорируют. Конфигурации справа рассматриваются в порядке очереди. Программа машины M хранится в конечном управлении M ’ . Обработка текущей конфигурации на первой ленте состоит в следующем:

Машина M ’ проверяет состояние и обозреваемый символ и, если состояние допускающее, также переходит в допускающее состояние.

Если состояние не допускающее и из данной конфигурации есть k переходов, то M ’ использует вторую ленту для создания k копий, которые записываются в конце очереди на ленте 1.

M ’ изменяет k конфигураций в соответствии с программой машины M.

M ’ перемещает отметку текущей конфигурации на следующую справа и цикл повторяется с шага 1.

Допустим, что m есть максимальное число выборов машины M в любой конфигурации. Тогда существует одно начальное состояние M, не более m конфигураций, достижимых за 1 шаг, не более m 2 конфигураций, достижимых за 2 шага и т.д. Таким образом, после n переходов машина M может достичь не более 1+ m +m 2 +…+m n £ n×m n конфигураций. Порядок, в котором машина M ’ исследует конфигурации, называется “поиском в ширину”, т.е. M ’ исследует все достижимые конфигурации машины M за 0 шагов, достижимые за 1 шаг и т.д.

Допускающая конфигурация машины M будет рассмотрена машиной M ’ в числе первых n×m n конфигураций. Таким образом, если машина M допускает, то машина M ’ также допускает, т.е. L(M) = L(M ’ ).

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

Теорема. Если M недетерминированная машина Тьюринга с емкостной сложностью S(n), то найдется детерминированная машина Тьюринга M ’ с емкостной сложностью O(S 2 (n)) и L(M ’ ) = L(M).

Доказательство. Пусть M недетерминированная машина Тьюринга (возможно k-ленточная) с емкостной сложностью S(n). Тогда число различных конфигураций, в которые машина M может попасть из начальной с входом длины n, не превосходит некоторого числа c S (n) , точнее ½Q½(½X½+1) k S(n) (S(n)) k , где k – число лент. Тогда число переходов от конфигурации C 1 к конфигурации C 2 (С 1 ├ С 2) на любой из лент не превосходит c S (n) . Можно выяснить, существует ли переход С 1 ├ С 2 за 2i шагов, проверив для всех C 3 существует ли переход С 1 ├ С 3 и С 3 ├ С 2 за i шагов. После каждого обращения к процедуре число i уменьшается вдвое.

Идея моделирования машиной M ’ работы машины M приведена в доказательстве предыдущей теоремы. Стратегия работы машины M ’ -

установить приведет ли начальная конфигурация C 0 к какой-нибудь допускающей конфигурации C f . Чтобы найти верхнюю емкостную границу для машины M ’ , расположим конфигурации (длины O(S(n))) на стеках того же размера. В каждый момент времени число фрагментов стека не превосходит 1+ log éc S (n) ù , т.е. O(S(n)). Для всего стека машины M потребуется O(S 2 (n)) ячеек.

Теорема. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга M = (X, Q, q 0 , F, I) с временной сложностью T(n), то он допускается одноленточной недетерминированной машиной с временной сложностью O(T 2 (n)).

Доказательство. Пусть M 1 одноленточная недетерминированная машина Тьюринга, имеющая на ленте 2k дорожек, т.е. ленточные символы машины M 1 представляются 2k-членными кортежами, в которых на нечетных местах стоят символы алфавита X, а на четных – либо символ L, либо маркер #. Дорожки с нечетными номерами соответствуют k лентам машины M, а каждая дорожка с четным номером 2j содержит символ L во всех ячейках, кроме одной, где стоит маркер #, отмечающий положение головки машины M на ленте j, которой соответствует дорожка 2j-1. Машина M 1 моделирует один шаг работы машины M следующим образом. Допустим, что вначале головка машины M 1 обозревает клетку, содержащую самую левую головку машины M.

Головка машины M 1 движется вправо, пока не минует все k маркеров положений головок на дорожках с четными номерами. При этом M 1 запоминает в своем состоянии символы, обозреваемые каждой из головок машины M. Теперь M 1 делает недетерминированное развлетвление, исходя из состояния машины M, которое машина M 1 запомнила в своем состоянии, и обозреваемых машиной M на лентах символов, которые машина M 1 также нашла.

Выбрав для моделирования шаг машины M, машина M 1 изменяет в соответствии с ним состояние машины M, которое она помнит в своем состоянии. Затем M 1 сдвигает свою головку влево и проходит все маркеры, изменяя ленточный символ на дорожке над маркером и сдвигая маркер не более чем на одну клетку (L,R,S).

Машина M 1 промоделировала один шаг работы машмны M. Действия машины M 1 на этом шаге детерминированы. Ее головка находится правее левого маркера не более чем на две ячейки. Начиная с этого маркера цикл можно повторить.

Если машина M допускает цепочку w длины n, то совершает при этом не более T(n) переходов. Очевидно, что в последовательности из T(n) шагов головки мащины M могут разойтись не более чем на T(n) клеток, и, значит, M 1 может смоделировать один шаг этой последовательности не более чем за O(T(n)) своих шагов. Таким образом, M 1 допускает цепочку w, выполняя не более чем O(T 2 (n)) переходов. Отсюда следует, что M 1 допускает язык L и имеет временную сложность O(T 2 (n)).

Следствие 1. Если язык допускается k-ленточной детерминированной машиной Тьюринга с временной сложностью T(n), то он допускается одноленточной детерминированной машиной Тьюринга с временной сложностью O(T 2 (n)).

Следствие 2 . Если язык L допускается k-ленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n).

Следствие 3. Если язык допускается k-ленточной детерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной детерминированной машиной Тьюринга с емкостной сложностью S(n).

Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.

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

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

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

Наряду с процессором и памятью компьютеру необходимы еще устройства ввода/вывода.

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

Для имитации компьютера на машине Тьюринга существенны две вещи:

Существуют ли инструкции, выполняемые компьютером, и недоступные для машины Тьюринга;

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

Неформальная модель реального компьютера :

Память, состоящая из последовательности слов и их адресов. В качестве адресов будут использоваться натуральные числа 0,1, …;

Программа компьютера, записанная в слова памяти, каждое из которых представляет простую инструкцию. Допускается “непрямая адресация” по указателям;

Каждая инструкция использует конечное число слов и изменяет значение не более одного слова;

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

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

представлена на рис.

Рис стр 369

Машина имеет несколько лент. Первая лента представляет всю память компьютера – адреса и значения (в двоичной системе). Адреса заканчиваются маркером *, значения – маркером #. Начало и конец записей 1-й ленты обозначаются маркером $. Вторая лента – “счетчик инструкций”, содержит одно двоичное целое, представляющее одну из позиций считываюшей головки на первой ленте, адрес инструкции, которая должна быть выполнена следующей. Третья лента содержит адрес и значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции машина Тьюринга должна найти значение по одному или нескольким адресам памяти, где хранятся данные, участвующие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения. Значение по этому адресу копируется на третью ленту и перемещается на нужное место, как правило, по одному из начальных адресов, представляющих регистры компьютера. Четвертая лента имитирует входной файл. Пятая лента - рабочая память, служит для выполнения вычислений. Допускающая инструкция машины Тьюринга соответствует выводу на печать в выходном файле.

Функционирование такой имитирующей машины:

1.Найдя на 1-й ленте адрес, совпадающий с номером инструкции на 2-й ленте, исследуем значение по нему и копируем на 3-ю ленту. Первые биты инструкции задают действие (копировать, вставить, ветвиться и т.д.), оставщиеся биты – адрес или адреса, используемые в этом действии.

2. Если в инструкции содержится значение по некоторому адресу, то этот адрес копируется на 3-ю ленту, а позиция инструкции на 2-ю дорожку 1-й ленты.

a) скопировать по другому адресу;

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

(1) на рабочую ленту копируется часть ленты справа от того места, куда надо поместить новое значение;

(2) новое значение записывается на 1-ю ленту;

(3) рабочая часть копируется обратно на 1-ю ленту справа от нового значения.

b) прибавить найденное значение по другому адресу;

Ищем второй адрес на первой ленте, выполняем сложение значения по этому адресу и записанному на 3-й ленте.

c) перейти к выполнению инструкции по адресу, записанному на 3-й ленте, для чего лента 3 копируется на ленту 2, и цикл инструкций начинается снова.

4. Выполнив инструкцию (не являющуюся переходом), прибавляем 1 к счетчику на ленте 2 и вновь начинаем цикл инструкции.

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

Время работы машины Тьюринга, имитирующей компьютер

Введем следующие ограничения на модель компьютера:

Ни одна компьютерная инструкция не должна порождать слово, длиннее, чем на 1 бит, своих операндов.

Инструкция, применяемая к словам длины m должна выполняться не более, чем за 0(m 2) шагов на многоленточной машине Тьюринга.

Назовем такие операции допустимыми.

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

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

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

После выполнения n шагов компьютер не может породить слово, длиннее c+n, и не может создать или использовать адрес, занимающий больше c+n битов. Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому после выполнения n инструкций имеем d+n адресов. Каждый адрес-значение занимает не более 2(c+n) +2 разрядов, а после выполнения n инструкций не больше 2(d+n)(c+n+1), или 0(n 2)

Для просмотра адресов одной инструкции компьютера требуется времени 0(n 2), слова имеют длину 0(n), а инструкции выполняются машиной Тьюринга за время 0(n 2), сдвиг для создания пространства для нового слова включает копирование данных объемом 0(n 2) с ленты 1 на рабочую ленту и обратно. Таким образом, машина Тьюринга имитирует один шаг компьютера за 0(n 2) своих шагов, а n шагов можно проимитировать за 0(n 3) шагов машины Тьюринга.

Теорема. Выполнение n шагов работы компьютера можно проимитировать на одноленточной машине Тьюринга не более чем за 0(n 6) шагов.

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

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

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

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

Таким образом Машина Тьюринга формально описывается набором двух алфавитов:

A={a1, a2, a3, …, an} — внешний алфавит, служит для записи исходных данных

Q={q1, q2, q3,…, qm} — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = {a0,a1,…,an} (В нашем случае A={0, 1})

Допустимые действия Машины Тьюринга таковы:

1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

Машина Тьюринга — это автомат, который управляется таблицей.

Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = {q0,q1,…,qm}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «<» (влево) или «.» (на месте)
· новое состояние автомата

В приведенной выше таблице алфавит A ={0, 1, _} (содержит 3 символа), а внутренний алфавит Q={q1, q2, q3, q4, q0}, q0 — состояние, заставляющее каретку остановиться.

Рассмотрим несколько задач решением. Скачать машину Тьюринга Вы можете на сайте в разделе СКАЧАТЬ .

Задача 1. Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Теперь определимся с состояниями каретки. Я называю их — «желания каретки что-то сделать».

q1) Каретка должна пойти вправо: если видит 0 меняет его на 1 и остается в состоянии q1, если видит 1 — меняет его на 0 и остается в состоянии q1, если видит _ — возвращается назад на 1 ячейку «желает что-то другое», т. е. переходит в состояние q2. Запишем наши рассуждения в таблицу исполнителя. Синтаксис смотрите в справке к программе)

q2) Теперь опишем «желание каретки» q2. Мы должны вернуться в первоначальное положение. Для этого: если видим 1 оставляем ее и остаемся в состоянии q2 (с тем же желанием дойти до конца ряда символов); если видим 0 — оставляем его и продолжаем двигаться влево в состоянии q2; видим _ — сдвигается вправо на 1 ячейку. Вот вы оказались там, где требуется в условии задачи. переходим в состояние q0.

Посмотреть работу программы можно на видео:

Задача 2. Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0. Например:

Из 001101011101 получим 000000000000 1111111.

Как видите, семь единиц записались после данной последовательности, а на их местах стоят нолики.

Приступим к рассуждениям. Определим, какие состояния необходимы каретке и сколько.

q1) увидел 1 — исправь на нолик и перейди в другое состояние q2 (новое состояние вводится, чтобы каретка не поменяла на нули все единицы за один проход)

q2) ничего не менять, двигаться к концу последовательности

q3) как только каретка увидела пустую ячейку, она делает шаг вправо и рисует единичку, если она видит единичку — то движется дальше, чтобы подписать символ в конце. Как только нарисовал единицу, переходим в состояние q4

q4) проходим по написанным единицам, ничего не меняя. Как только доходим до пустой ячейки, разделяющей последовательность от единиц, переходим с новое состояние q5

q5) в этом состоянии идем начало последовательности, ничего не меняя. Доходим до пустой ячейки, разворачиваемся и переходим в состояние q1

Состояние q0 каретка примет в том случае, когда она пройдет в состоянии q1 до конца данной последовательности и встретит пустую ячейку.

Получим такую программу:

Работу Машины Тьюринга можете посмотреть на видео ниже.

Машина Тьюринга - одно из самых интригующих и захватывающих интеллектуальных открытий 20-го века. Это простая и полезная абстрактная модель вычислений (компьютерных и цифровых), которая является достаточно общей для воплощения любой компьютерной задачи. Благодаря простому описанию и проведению математического анализа она образует фундамент теоретической информатики. Это исследование привело к более глубокому познанию цифровых компьютеров и исчислений, включая понимание того, что существуют некоторые вычислительные проблемы, не решаемые на общих пользовательских ЭВМ.

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

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

Каждая машина связывает два конечных ряда данных: алфавит входящих символов A = {a0, a1, ..., am} и алфавит состояний Q = {q0, q1, ..., qp}. Состояние q0 называют пассивным. Считается, что устройство заканчивает свою работу, когда попадает именно на него. Состояние q1 называют начальным - машина начинает свои вычисления, находясь на старте в нем. Входное слово располагается на ленте по одной букве подряд в каждой позиции. С обеих сторон от него располагаются только пустые ячейки.

Как работает механизм

Машина Тьюринга имеет принципиальное отличие от вычислительных устройств – ее запоминающее приспособление имеет бесконечную ленту, тогда как у цифровых аппаратов такое устройство имеет полосу определенной длины. Каждый класс заданий решает только одна построенная машина Тьюринга. Задачи иного вида предполагают написание нового алгоритма. Управляющее устройство, находясь в одном состоянии, может передвигаться в любую сторону по ленте. Оно записывает в ячейки и считывает с них символы конечного алфавита. В процессе перемещения выделяется пустой элемент, который заполняет позиции, не содержащие входные данные. Алгоритм для машины Тьюринга определяет правила перехода для управляющего устройства. Они задают головке записи-чтения такие параметры: запись в ячейку нового символа, переход в новое состояние, перемещение влево или вправо по ленте.

Свойства механизма

Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов: Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1. Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо. Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны. Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0. Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит. Функции машины Тьюринга В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В – слова в рамках двоичного кодового алфавита В={0.1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.-

Программа для устройства

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

Составляющие для вычислений

Чтобы построить машину Тьюринга для решения одной определенной задачи, необходимо определить для нее следующие параметры. Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них - а0 - должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = {0, 1, а0}. Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом. Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q={q1, q2...}. Одно из таких положений - q1 - должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.

Таблица переходов.

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

Алгоритм для автомата

Кареткой устройства Тьюринга во время работы управляет программа, которая во время каждого шага выполняет последовательность следующих действий: Запись символа внешнего алфавита в позицию, в том числе и пустого, осуществляя замену находившегося в ней, в том числе и пустого, элемента. Перемещение на один шаг-ячейку влево или же вправо. Изменение своего внутреннего состояния. Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: ai – элемент из выбранного алфавита A, направление сдвига каретки ("←” влево, "→” вправо, "точка” - отсутствие перемещения) и qk - новое состояние устройства. К примеру, команда 1 "←” q2 имеет значение "заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q2”.

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

В каждой машине Тьюринга есть две части:

1) неограниченная в обе стороны лента , разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита : алфавит входных символов A = {a 0 , a 1 , ..., a m }и алфавит состояний Q = {q 0 , q 1 , ..., q p }. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q .) Состояние q 0 называется пассивным . Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q 1 называется начальным . Находясь в этом состоянии, машина начинает свою работу.

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

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

Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую буквуai он видит, а также в зависимости от своего состояния qj автомат может выполнять следующие действия:

· записать новую букву в обозреваемую ячейку;
· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
· перейти в новое состояние.

То есть у машины Тьюринга есть три вида операций. Каждый раз для очередной пары (q j , a i ) машина Тьюринга выполняет команду, состоящую из трех операций с определенными параметрами.

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

Клетка (q j , a i ) определяется двумя параметрами - символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).

После выполнения автоматом очередной команды он переходит в состояние q m (которое может в частном случае совпадать с прежним состоянием q j ). Следующую команду нужно искать в m -й строке таблицы на пересечении со столбцом a l (букву a l автомат видит после сдвига).

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

Несмотря на свое простое устройство, машина Тьюринга может выполнять все возможные преобразования слов, реализуя тем самым все возможные алгоритмы.

Машина Поста

Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой - 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

1) V j - поставить метку, перейти к j-й строке программы.

2) X j - стереть метку, перейти к j-й строке программы.

3) <- j - сдвинуться влево, перейти к j-й строке программы.

a. j - сдвинуться вправо, перейти к j-й строке программы.

4) ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

5) ! – конец программы (стоп).

У команды «стоп» отсылки нет. После запуска возможны варианты:

Работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

Что это и кто создал

Из чего состоит устройство

Каждая такая машина состоит из двух составляющих:

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

Как работает механизм

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

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

Свойства механизма

Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов:

Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1.
Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо.
Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны.
Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0.
Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит.

Функции машины Тьюринга

В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В - слова в рамках двоичного кодового алфавита В={0.1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.

Программа для устройства

Составляющие для вычислений

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

Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них - а0 - должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = {0, 1, а0}.

Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом.

Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q={q1, q2...}. Одно из таких положений - q1 - должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.

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

Алгоритм для автомата

Кареткой устройства Тьюринга во время работы управляет программа, которая во время каждого шага выполняет последовательность следующих действий:

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

Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: a i - элемент из выбранного алфавита A, направление сдвига каретки ("←” влево, "→” вправо, "точка” — отсутствие перемещения) и q k - новое состояние устройства. К примеру, команда 1 "←” q 2 имеет значение "заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q 2 ”.

Машина Тьюринга: примеры

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

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

Здесь q 1 — состояние изменения цифры, q 0 — остановка. Если в q 1 автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q 0 , то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q 1 . Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q 0 - остановка.

Пример 2. Дан ряд из символов, обозначающих открывающие и закрывающие скобки. Требуется построить устройство Тьюринга, которое выполняло бы удаление пары взаимных скобок, то есть элементов, расположенных подряд - “()”. Например, исходные данные: “) (() (()”, ответ должен быть таким: “) . . . ((”. Решение: механизм, находясь в q 1 , анализирует крайний слева элемент в строке.

Состояние q 1: если встречен символ “(”, то совершить сдвиг вправо и переход в положение q 2 ; если определен “a 0 ”, то остановка.

Состояние q 2: проводится анализ скобки “(” на наличие парности, в случае совпадения должно получиться “)”. Если элемент парный, то сделать возврат каретки влево и перейти в q 3 .

Состояние q 3: осуществить удаление сначала символа “(”, а затем “)” и перейти в q 1 .