Машина Тьюринга — различия между версиями
м (→Многодорожечная машина Тьюринга) |
м (→Многодорожечная машина Тьюринга: очень важная ремарка) |
||
Строка 138: | Строка 138: | ||
=== Многодорожечная машина Тьюринга === | === Многодорожечная машина Тьюринга === | ||
− | Машиной Тьюринга с <tex>n</tex> дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из <tex>n</tex> дорожек, на каждой из которых записаны символы алфавита. Соответственно, функция перехода имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}</tex>. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом <tex>\Pi' = \Pi^n</tex>. | + | Машиной Тьюринга с <tex>n</tex> дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из <tex>n</tex> дорожек, на каждой из которых записаны символы ленточного алфавита. Соответственно, функция перехода имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}</tex>. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом <tex>\Pi' = \Pi^n</tex>. |
=== Машина Тьюринга с полубесконечной лентой === | === Машина Тьюринга с полубесконечной лентой === |
Версия 00:37, 7 декабря 2012
Машина Тьюринга (Turing machine) — абстрактный вычислитель, предложенный британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
- бесконечной одномерной ленты, разделённой на ячейки,
- головкой, которая представляет собой детерминированный конечный автомат.
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
Содержание
Определение
Определение машины
Определение: |
Формально машина Тьюринга определяется как кортеж из восьми элементов
| , где
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.
Определение процесса работы
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ
. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую на ленту.Определение: |
Назовём конфигурацией машины Тьюринга тройку | , где — текущее состояние автомата, а — строки слева и справа от головки до первого пробельного символа соответственно.
В данной записи головка находится над ячейкой, на которой написана первая буква
(или , если ).В дальнейшем используются следующие обозначения:
,Определение: |
Определим на конфигурациях отношение перехода
Особо следует рассмотреть случай переходов по пробельному символу:
| :
Очевидно, что определённое отношение является функциональным: для каждой конфигурации
существует не более одной конфигурации , для которой .Для машины Тьюринга, которая пишет символ
на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода. Это предоставляется читателю в качестве упражнения.Результат работы
Машину Тьюринга можно рассматривать как распознаватель слов языка. Пусть
— машина Тьюринга, распознаваемый ей язык определяется как .Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина
задаёт вычислимую функцию , причём . Переход автомата в состояние можно интерпретировать как аварийное завершение программы (например, при некорретном входе).Примеры машин-распознавателей и машин-преобразователей будут даны ниже.
Примеры машин Тьюринга
Прибавление единицы
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
- в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
- встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние ,
- в состоянии головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
- встретив в состоянии пробельный символ, головка перемещается на один символ вправо и переходит в состояние , завершая работу.
Формально:
, , . Таблица функции приведена ниже:Проверка того, является ли слово палиндромом
В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом
. Алгоритм следующий:- если строка на ленте — пустая, то перейти в допускающее состояние
- надо запомнить первый символ слова в состоянии автомата,
- стереть его,
- перейти в конец ленты:
- если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
- если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
- в случае несовпадения перейти в отвергающее состояние
Формально:
, , . Таблица функции приведена ниже:Варианты машины Тьюринга
В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности.
Многодорожечная машина Тьюринга
Машиной Тьюринга с
дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из дорожек, на каждой из которых записаны символы ленточного алфавита. Соответственно, функция перехода имеет тип . Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом .Машина Тьюринга с полубесконечной лентой
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой следующим образом: в первой ячейке записывается символ
(подразумевается, что он не является ленточным символом исходной машины), который сигнализирует о том, что нужно перейти с дорожки на дорожку и двигаться в обратном направлении. Это реализуется с помощью создания копий всех состояний исходного автомата, при этом правила для копии используют для чтения и записи вторую ленту и перемещают головку в противоположном направлении.Многоленточная машина Тьюринга
В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу перемещаться по-разному. То есть, функция перехода теперь имеет тип
.Многоленточная машина с
дорожками эмулируется машиной с дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов
символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.Другие эквивалентные вычислительные формализмы
Существуют также другие формализации понятия алгоритма, которые по вычислительным возможностям эквивалентны машинам Тьюринга:
- стековые машины
- счётчиковые машины
- клеточные автоматы
- произвольные формальные грамматики
- нетипизированное лямбда-исчисление
Универсальная машина Тьюринга
Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, универсальный язык перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.