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

Модели вычислителей

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

Конечный автомат (КА)

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

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

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

Функционирование автомата удобно представлять графически. При получении входного сигнала конечный автомат выдает информацию на выход как функцию этого входного сигнала и текущего состояния и меняет свое внутреннее состояние. На рисунке блок памяти автомата хранит информацию о текущем состоянии S, которое вместе с входным сигналом X определяет выходную реакцию автомата У и следующее состояние.

В качестве примера опишем с помощью конечного автомата поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Задавать автомат удобно ориентированным графом, в котором вершины соответствуют состояниям, а дуга из состояния s в состояние q, помеченное х/у, проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией у. Граф автомата, моделирующего умное поведение родителя, представлен на рисунке.

Автомат, описывающий поведение «умного» отца

Этот автомат имеет четыре состояния {s0, s1, s2, s3} и два входных сигнала — оценки, полученные сыном в школе: {2,5}. Начиная с начального состояния s0 (оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы — реакции на входы. Выходы автомата {у0,..., у5} будем интерпретировать как действия родителя так:

у0: — брать ремень;

у1: — ругать сына;

у2: — успокаивать сына;

уЗ: — надеяться;

у4: — радоваться;

у5: — ликовать.

Сына, получившего одну и ту же оценку — двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Отец помнит, как его сын учился раньше, и строит свое воспитание с учетом его предыдущих успехов и неудач. Например, после третьей двойки в истории 2,2,2 сына встретят ремнем, а в истории 2, 2, 5, 2 — будут успокаивать. Каждая предыстория определяет текущее состояние автомата, при этом некоторые входные предыстории эквивалентны (именно те, которые приводят автомат в одно и то же состояние): история 2,2,5 эквивалентна пустой истории, которой соответствует начальное состояние.

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

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

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

Из-за ограниченной внутренней памяти и отсутствия внешней КА может реализовать только узкий класс задач.

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

МТ состоит из 2 частей: ленты и конечного автомата. Лента неподвижна, а головка движется относительно ленты под управлением автомата (влево, вправо, стоит на месте).

МТ может выполнять следующие команды:

1) записывать в ячейку ленты новый символ;

2) сдвигаться на одну ячейку влево или вправо;

3) переходить в новое внутреннее состояние.

Больше МТ ничего не может.

МТ задается:

1) набором внутренних состояний Q={q₁…q_n};

2) входным алфавитом S={s₁…s_k);

3) командами движения головки {L,R,N}.

4) программой управления, которую удобно задавать в табличной форме.

Автомат останавливается по команде stop (!) в определенном состоянии (конфигурации) <s,q>.

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

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

Рассмотрим примеры решения задач с помощью машины Тьюринга.

Пример 1.

Сокращенная запись:

Пример 2.

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

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

Пример. Вычислить сумму 2-х чисел в 2СС

Исходные данные

**001100111** //символы на ленте 1

**100111100** //символы на ленте 2

************* //символы на ленте 3

Головки обозревают первые символы лент

Состояния (процессы) выполнения задачи

q0 – поиск начала записанных чисел

q1 – движение головок вдоль чисел до последнего

q2 – сложение чисел и запись результата на 3-ю ленту

q3 – сложение чисел с учетом переноса

q4 – конечное состояние, останов МТ

Команды 3-ленточной МТ, выполняющей сложение 2 чисел в 2СС

q, S₁, S₂, S₃ -> q’, S₁’, S₂’, S₃’, Г₁, Г₂, Г₃

0,*,*,*>0,*,*,*,R,R,R

0,0,0,*>1,0,0,*,R,R,R

0,1,0,*>1,1,0,*,R,R,R

0,0,1,*>1,0,1,*,R,R,R

0,1,1,*>1,1,1,*,R,R,R

1,0,0,*>1,0,0,*,R,R,R

1,1,0,*>1,1,0,*,R,R,R

1,0,1,*>1,0,1,*,R,R,R

1,1,1,*>1,1,1,*,R,R,R

1,*,*,*>2,*,*,*,L,L,L

2,0,0,*>2,0,0,0,L,L,L

2,0,1,*>2,0,1,1,L,L,L

2,1,0,*>2,1,0,1,L,L,L

2,1,1,*>3,1,1,0,L,L,L

2,*,*,*>4,*,*,*,S,S,S

3,0,0,*>2,0,0,1,L,L,L

3,*,*,*>2,*,*,1,L,L,L

3,0,1,*>3,0,1,0,L,L,L

3,1,0,*>3,1,0,0,L,L,L

3,1,1,*>3,1,1,1,L,L,L

Программа в табличном виде

Вн. сост.	,,*	0,0,*	1,0,*	0,1,*	1,1,*
q0	q0,,,*,R,R,R	q1,0,0,*,R,R,R	q1,1,0,*,R,R,R	q1,0,1,*,R,R,R	q1,1,1,*,R,R,R
q1	q2,,,*,L,L,L	q1,0,0,*,R,R,R	q1,1,0,*,R,R,R	q1,0,1,*,R,R,R	q1,1,1,*,R,R,R
q2	q4,,,*,S,S,S	q2,0,0,0,L,L,L	q2,0,1,1,L,L,L	q2,1,0,1,L,L,L	q3,1,1,0,L,L,L
q3	q2,,,1,L,L,L	q2,0,0,1,L,L,L	q3,1,0,0,L,L,L	q3,0,1,0,L,L,L	q3,1,1,1,L,L,L

Дата добавления: 2022-01-22; просмотров: 27; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!