Машина Тьюринга. Устройство. Состояние. Конфигурация.

Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического устройства. Лента выступает в качестве внешней памяти; она считается не­ограниченной (бесконечной) — уже это свидетельствует о том, что машина Тьюринга является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконеч­ного размера.

Как и в машине Поста, лента разбита на отдельные ячейки, однако, в машине Тьюринга неподвижной является головка, а лен­та передвигается относительно нее вправо или влево. Другим от­личием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите А= <Δ, а1, . ап>— этот алфавит называется внешним. В нем выделяется специальный символ — Δ, называемый пустым знаком. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, от­личных от пустого знака.

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

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

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (аi), а на другой вход — знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания зна­ков (аi, qi> и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (аi+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (qi+1). Таким образом, элементарный шаг (такт) работы ма­шины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего со­стояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние.

В схеме функционирования машины Тьюринга отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты — она предназначена для хранения информа­ции, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохра­няется следующее состояние (qi+1), а в D — команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.

Общее правило, по которому работает машина Тьюринга, мож­но представить следующей записью: qiaj® , т.е. после обзора символа аj головкой в состоянии qi, в ячейку записывается символ аj’, головка переходит в состояние qi’, а лента совершает движение Dk.

Конкретная машина Тьюринга задается перечислением эле­ментов множеств А и Q, а также, логической функцией, которую реализует ЛУ, т.е. набором правил преобразования. Ясно, что различных множеств A, Q и логических функций может быть бес­конечно много, т.е. и машин Тьюринга также бесконечно много.

Совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки называется конфигурацией машины

58. Нормальные алгоритмы Маркова. Сравнение алгоритмических схем Маркова и Тьюринга.

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

Рассмотрим некоторый алфавит А,содержащий конечное число знаков (букв). Введем ряд определений:

Слово– это любая конечная последовательность знаков алфавита.

Число символов в слове называется его длиной.

Слово, длина которого равна нулю, называется пустым.

Слово s называется подсловомслова q, если q можно представить в виде q=rst, где r и t – любые слова в том же алфавите (в том числе и пустые).

Теперь можно определить понятие алгоритма (не являющееся строгим):

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

В алгоритмах Маркова в качестве элементарного шага алго­ритма принимается подстановка одного слова вместо другого. Пусть в алфавите А построено исходное слово Р,которое содер­жит подслово Р_r (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово P_k в том же алфавите.

Подстановкойназывается замена первого по порядку подслова Р_r исходного слова Р на слово P_k. Обозначается подстановка P_r ® P_k.

Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в Р,то первая из нихприменяется к Р, в результате чего оно переходит в другое слово Р₁. К нему вновь применяется схема подстановок и т.д. Процесс прекращает­ся в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Р_п,либо при получении Р_п была применена последняя подстановка.

Пример.

Пусть задан алфавит А = <*,1>и единственная подстановка: *1®1. Най­ти результат обработки, если исходным является слово Р = 11*111*1. Применение нормального алгоритма с указанной подстановкой к дан­ному слову дает последовательность (подчеркиванием выделяется преобразуемая комбинация):

11*111*1®11111*1®111111, т.е. алгоритм находит количество единиц в исходном слове (суммирует числа в унарной системе счисления).

Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами допустимых подстановок. Нормальный алгоритм Маркова можно рассматривать как стандартную форму для задания любого алгоритма. Данная форма представления алгоритма важна не только с точки зрения проведения исследова­ний в теории алгоритмов, но она послужила основой специализи­рованного языка символьных преобразований в системах искусст­венного интеллекта.

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

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

Содержание

Устройство машины Тьюринга

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки [2] [3] , и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Запись правила «q_ia_j→q_i1a_j1R/L/N» следует понимать так: q_i — состояние при котором выполняется это правило, a_j — данные в ячейке, в которой находится головка, q_i1 — состояние в которое нужно перейти, a_j1 — что нужно записать в ячейку, R/L/N — команда на перемещение.

Машина работает по следующему набору правил:

q0	q1	q2	q3	q4	q5	q6	q7	q8
1	q01→q01R	q11→q2aR	q21→q21L	q31 → q4aR	q41→q41R	q71→q2aR
×	q0×→q1×R	q2×→q3×L	q4×→q4×R	q6×→q7×R	q8×→q9×N
=	q2=→q2=L	q4=→q4=R	q7=→q8=L
a	q2a→q2aL	q3a→q3aL	q4a→q4aR	q6a→q61R	q7a→q7aR	q8a→q81L
*	q0*→q0*R	q3*→q6*R	q4*→q51R
q5 →q2*L

Начало
q0	начальное состояние. Ищем «x» справа. При нахождении переходим в состояние q1
q1	заменяем «1» на «а» и переходим в состояние q2
Переносим все «1» из первого числа в результат
q2	ищем «х» слева. При нахождении переходим в состояние q3
q3	ищем «1» слева, заменяем её на «а» и переходим в состояние q4. В случае если «1» закончились, находим «*» и переходим в состояние q6
q4	переходим в конец (ищем «*» справа), заменяем «*» на «1» и переходим в состояние q5
q5	добавляем «*» в конец и переходим в состояние q2
Обрабатываем каждый разряд второго числа
q6	ищем «х» справа и переходим в состояние q7. Пока ищем заменяем «а» на «1»
q7	ищем «1» или «=» справа при нахождении «1» заменяем его на «а» и переходим в состояние q2 при нахождении «=» переходим в состояние q8
Конец
q8	ищем «х» слева. При нахождении переходим в состояние q9. Пока ищем заменяем «а» на «1»
q9	терминальное состояние (остановка алгоритма)

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

Начало. Находимся в состоянии q₀, ввели в машину данные: *111×11=*, головка машины располагается на первом символе *.

1-й шаг. Смотрим по таблице правил что будет делать машина, находясь в состоянии q₀ и над символом «*». Это правило из 1-го столбца 5-й строки — q₀*→q₀*R. Это значит, что мы переходим в состояние q₀ (то есть не меняем его), символ станет «*» (то есть не изменится) и смещаемся по введённому нами тексту «*111×11=*» вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q₀1 (1-й столбец 1-я строка) обрабатывается правилом q₀1→q₀1R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ «х». И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.

Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву «а», и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на «а» и дописывания такого же количества единиц в конце строки (слева от крайнего правого «*»). Затем меняем все «а» до знака умножения «х» обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой «а» и снова переносим единицы. Когда до знака «=» не окажется единиц — значит умножение завершено.

Полнота по Тьюрингу

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

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

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

Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины D <\displaystyle D> и входные данные X <\displaystyle X> , которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные X <\displaystyle X> .

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

На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но, тем не менее, всегда конечна. Теоретический предел количества информации, которая может находиться внутри заданной поверхности, с точностью до множителя 1 / ln ⁡ 2 <\displaystyle 1/\ln <2>> равен энтропии чёрной дыры с той же площадью поверхности.

Варианты машины Тьюринга

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

Машина Тьюринга, работающая на полубесконечной ленте

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

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых, произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.