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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a		1	2	3	.	7	8	9
q₁	1 H q	1 H q	2 H q	3 H q	4 H q	.	8 H q	9 H q	0 λ q₁

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

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

a	(	)
q₁	a H q	( П q₂	) П q₁
q₂	a H q	( П q₂	) λ q₃
q₃	a H q	a П q₃	a П q1

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

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

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

Машина Тьюринга

Содержание

Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:

бесконечной одномерной ленты, разделённой на ячейки,
головки, которая представляет собой детерминированный конечный автомат.

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

Читайте также: Тест драйв джели мгрант

Определение [ править ]

Определение машины [ править ]

Определение:

Формально машина Тьюринга (англ. Turing machine) определяется как кортеж из восьми элементов [math]\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle[/math] , где

[math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова,
[math]\Pi \supset \Sigma[/math] — символы, которые могут быть записаны на ленту в процессе работы машины,
[math]B \in \Pi \setminus \Sigma[/math] — пробельный символ (от слова blank),
[math]Q[/math] — множество состояний управляющего автомата,
[math]Y \in Q[/math] — допускающее состояние автомата,
[math]N \in Q[/math] — отвергающее состояние автомата,
[math]S \in Q[/math] — стартовое состояние автомата,
[math]\delta : Q \times \Pi \to Q \times \Pi \times \< \leftarrow, \rightarrow, \downarrow \>[/math] — всюду определённая функция перехода автомата.

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

Определение процесса работы [ править ]

Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ [math]B[/math] . Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую [math]B[/math] на ленту.

Определение:

Назовём конфигурацией машины Тьюринга тройку [math]\langle w, q, v \rangle[/math] , где

[math]q \in Q[/math] — текущее состояние автомата,
[math]w, v \in (\Pi \setminus \)^*[/math] — строки слева и справа от головки до первого пробельного символа соответственно.

В данной записи головка находится над ячейкой, на которой написана первая буква [math]v[/math] (или [math]B[/math] , если [math]v = \varepsilon[/math] ).

В дальнейшем используются следующие обозначения: [math]x, y, z \in \Pi[/math] , [math]w, v \in \Pi^*[/math]

Определение:

Определим на конфигурациях отношение перехода [math]\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle[/math] :

если [math]\delta(q, x) = \langle p, y, \leftarrow \rangle[/math] , то [math]\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle[/math] ,
если [math]\delta(q, x) = \langle p, y, \rightarrow \rangle[/math] , то [math]\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle[/math] ,
если [math]\delta(q, x) = \langle p, y, \downarrow \rangle[/math] , то [math]\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle[/math] .

Особо следует рассмотреть случай переходов по пробельному символу:

если [math]\delta(q, B) = \langle p, y, \leftarrow \rangle[/math] , то [math]\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle[/math] ,
если [math]\delta(q, B) = \langle p, y, \rightarrow \rangle[/math] , то [math]\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle[/math] ,
если [math]\delta(q, B) = \langle p, y, \downarrow \rangle[/math] , то [math]\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle[/math] .

Очевидно, что определённое отношение является функциональным: для каждой конфигурации [math]C[/math] существует не более одной конфигурации [math]C'[/math] , для которой [math]C \vdash C'[/math] .

Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

Результат работы [ править ]

Машину Тьюринга можно рассматривать как распознаватель слов формального языка. Пусть [math]M[/math] — машина Тьюринга, распознаваемый ей язык определяется как [math]\mathcal L(M) = \< x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \>[/math] .

Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина [math]M[/math] задаёт вычислимую функцию [math]f[/math] , причём [math]f(x) = y \Leftrightarrow \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle[/math] . Переход автомата в состояние [math]N[/math] можно интерпретировать как аварийное завершение программы (например, при некорретном входе).

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

Примеры машин Тьюринга [ править ]

Прибавление единицы [ править ]

Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:

в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние [math]R[/math] ,
в состоянии [math]R[/math] головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
встретив в состоянии [math]R[/math] пробельный символ, головка перемещается на один символ вправо и переходит в состояние [math]Y[/math] , завершая работу.

Формально: [math]\Sigma = \<0, 1 \>[/math] , [math]\Pi = \<0, 1, B\>[/math] , [math]Q = \[/math] . Таблица функции [math]\delta[/math] приведена ниже:

[math]0[/math]	[math]1[/math]	[math]B[/math]
[math]S[/math]	[math]\langle R, 1, \downarrow \rangle[/math]	[math]\langle S, 0, \rightarrow \rangle[/math]	[math]\langle R, B, \leftarrow \rangle[/math]
[math]R[/math]	[math]\langle R, 0, \leftarrow \rangle[/math]	[math]\langle R, 1, \leftarrow \rangle[/math]	[math]\langle Y, B, \rightarrow \rangle[/math]

Проверка того, является ли слово палиндромом [ править ]

В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом [math]\<0, 1\>[/math] . Алгоритм следующий:

если строка на ленте — пустая, то перейти в допускающее состояние
надо запомнить первый символ слова в состоянии автомата,
стереть его,
перейти в конец ленты:
- если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
- если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
- в случае несовпадения перейти в отвергающее состояние

Формально: [math]\Sigma = \<0, 1\>[/math] , [math]\Pi = \<0, 1, B\>[/math] , [math]Q = \[/math] . Таблица функции [math]\delta[/math] приведена ниже:

[math]0[/math]	[math]1[/math]	[math]B[/math]
[math]S[/math]	[math]\langle F_0, B, \rightarrow \rangle[/math]	[math]\langle F_1, B, \rightarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]F_0[/math]	[math]\langle F_0, 0, \rightarrow \rangle[/math]	[math]\langle F_0, 1, \rightarrow \rangle[/math]	[math]\langle B_0, B, \leftarrow \rangle[/math]
[math]F_1[/math]	[math]\langle F_1, 0, \rightarrow \rangle[/math]	[math]\langle F_1, 1, \rightarrow \rangle[/math]	[math]\langle B_1, B, \leftarrow \rangle[/math]
[math]B_0[/math]	[math]\langle R, B, \leftarrow \rangle[/math]	[math]\langle N, 1, \downarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]B_1[/math]	[math]\langle N, 0, \downarrow \rangle[/math]	[math]\langle R, B, \leftarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]R[/math]	[math]\langle R, 0, \leftarrow \rangle[/math]	[math]\langle R, 1, \leftarrow \rangle[/math]	[math]\langle S, B, \rightarrow \rangle[/math]

Варианты машины Тьюринга [ править ]

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

Многодорожечная машина Тьюринга [ править ]

Машиной Тьюринга с [math]n[/math] дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из [math]n[/math] дорожек, на каждой из которых записаны символы ленточного алфавита. У многодорожечной машины одна головка, которая за один шаг переходит в одном направлении на всех дорожках одновременно. Соответственно, функция перехода имеет тип [math]\delta : Q \times \Pi^n \to Q \times \Pi^n \times \<\leftarrow, \rightarrow, \downarrow\>[/math] . Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом [math]\Pi’ = \Pi^n[/math] .

Машина Тьюринга с полубесконечной лентой [ править ]

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

Доказательство: [math]\triangleright[/math]

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

Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ [math]c[/math] , значит головка достигла границы рабочей зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. [math]\triangleleft[/math]

Многоленточная машина Тьюринга [ править ]

В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могут перемещаться по-разному. То есть, функция перехода теперь имеет тип [math]\delta : Q \times \Pi^n \to Q \times \Pi^n \times \<\leftarrow, \rightarrow, \downarrow\>^n[/math] .

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

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

Универсальная машина Тьюринга [ править ]

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

➤

Утверждение (Тезис Чёрча-Тьюринга):