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

 

 

 

Решение

 

 

 

(1)		b	b	a	b	b
		q1
(2)
		L	b	a	b	b
			q3
(3)		L	b	a	b	b
				q3
(4)
		L	b	a	b	b
					q3
(5)
		L	b	a	b	b
						q3

 

 

9

 

(6)		L	b	a	b	b	L

q₃

 

(7)			L	b	a	b	b	b

q₀

 

 

Более короткая запись этой последовательности конфигураций, т. е. про-

 

цесса работы машины будет

 

q₁bbabb Þ Lq₃babb Þ Lbq₃ abb Þ Lbaq₃bb Þ

 

Þ Lbabq₃b Þ Lbabbq₃ L Þ babbb.

 

Таким образом, слово bbabb переработано машиной в слово babbb .

 

Пример	3.  Задается  машина  Тьюринга  внешним  алфави-
том A = {a,b, c},	алфавитом внутренних состояний Q = {q0 , q1, q2 , q3} и
программой:

 

q₁a ® q₁Лa, q₂a ® q₃ Пb, q₃a ® q₁Лa, q₁b ® q₂ Лa, q₂b ® q₂ Лb, q₃b ® q₃ Пb, q₁c ® q₀ a, q₂c ® q₂ Лc, q₂ L ® q₂ Ha, q₃c ® q₃ Пc.

 

Заметим, что программа этой машины может быть записана в виде следующей таблицы:

 

	q1	q2	q3
a	q1Лa	q3Пb	q1Лa
b	q2 Лa	q2 Лb	q3Пb
c	q0a	q2 Лc	q3 Пc

 

 

Для того чтобы  определить по таблице, что будет делать машина, нахо-дясь, например, в состоянии q₂ и наблюдая в обозреваемой ячейке символ b, нужно найти в таблице клетку, находящуюся на пересечении столбца q₂

 

и строки b. В этой клетке записано q ₂ bЛ . Это означает, что на следующем

 

10

 

шаге машина останется в прежнем состоянии q₂ , сохранит содержимое обозреваемой ячейки b и перейдет к обозрению следующей левой ячейки на ленте.

Предположим, что в начальной конфигурации головка находится над крайней правой клеткой.

 

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

bbcbq₁b Þ bbcq₂ba Þ bbq₂cba Þ bq₂bcba Þ q₂bbcba Þ q₂abbcba Þ

 

• bq₃bbcba Þ bbq₃bcba Þ bbbq₃cba Þ bbbcq₃ba Þ bbbcbq₃a Þ bbbcq₁ba Þ

 

• bbbq₂caa Þ bbq₂bca Þ bq₂bbca Þ q₂bbbca Þ q₂ abbbca Þ bq₃bbbca Þ

 

• bbq₃bbca Þ bbbq₃bca Þ bbbbq₃ca Þ bbbbcq₃ Þ bbbbq₁ca Þ bbbbq₀ aa.

 

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

 

Из приведенных  примеров следует, что МТ – это некоторое правило (алгоритм) для преобразования слов алфавита A È Q , т. е. конфигураций.

 

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

 

4. Способы задания  машин Тьюринга, операции над  ними

 

Рассмотрим три  основные операции, применяемые над машинами Тьюринга.

 

1. Пусть машины Тьюринга  Т₁   и Т₂ имеют соответственно про-

 

граммы П₁ и П₂. q¹₀ – заключительное состояние Т₁, q₁² – начальное со-

 

11

 

стояние Т₂. Предположим, что внутренние алфавиты этих машин не пе-

 

ресекаются. Заменим везде в программе П₁ состояние q¹₀ на состояние q₁² и полученную программу объединим с программой П₂. Новая про-

 

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

 

шин Т₁ и Т₂ (по паре состояний ( q¹₀ , q₁² )) и обозначается Т₁  Т₂ или Т₁Т₂ .

Более подробная  запись полученной машины будет выглядеть – Т = = Т(Т₁, Т₂, ( q¹₀ , q₁² )). Внешний алфавит композиции Т₁ Т₂ является объ-

 

единением алфавитов  машин Т₁ и Т₂.

 

2. Пусть q₀ – некоторое заключительное состояние машины Т, а q_k  –

 

какое-либо состояние этой же машины Т, не являющееся заключительным. Заменим всюду в программе П машины Т символ q₀ на q_k . В результате получим программу П’, которая определяет машину Т’ ( q₀ , q_k ). Машина Т’ называется итерацией машины Т по паре состояний ( q₀ , q_k ).

 

3. Пусть машины Тьюринга Т₁, Т₂ и Т₃ задаются программами П₁, П₂ и П ₃ соответственно. Внутренние алфавиты этих машин не пересекаются. Пусть q₀^' и q₀^'' – какие-либо заключительные состояния машины

Т₁. Заменим в программе П₁ состояние q₀^' некоторым начальным состоя-

нием q'  машины Т2,				а состояние	q''  некоторым начальным состоянием
	1				0
q"	машины Т3. Затем новую программу объединим с программами П2  и
1
П3.	Получим		программу   П,		задающую   машину   Тьюринга
Т = Т(Т1( q'		, q' ),Т2( q''		, q" ),Т3), которая называется разветвлением машин
	0	1	0	1

Т₂ и Т₃, управляемым машиной Т₁.

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

 

12

 

Операторную запись алгоритма представляет собой строку, состоя-

 

щую из символов, обозначающих машины, символов перехода (вида | q' и

 

k

q"|), а также символов a и w , служащих для обозначения соответственно

 

k

начала и окончания  работы алгоритма. В операторной записи (некоторого

 

алгоритма) выражение Тi | qi0	Тj …Tm qn1 | Tn  обозначает разветвление ма-
k	k

шин Т_j и T_n, управляемое машиной Т_i, причем заключительное состояние q_i0 машины Т_i заменяется начальным состоянием q_n1 машины T_n, а всякое другое заключительное состояние машины Т_i заменяется начальным со-стоянием машины Т_j (одним и тем же). Если машина Т_i имеет одно заклю-

 

чительное состояние, то символы | q_i0 и q_n1 |служат для обозначения безус-

ловного перехода. Там, где могут возникнуть недоразумения, символы q_i0 и q_n1 опускаются.

 

Пример 4. Операторная  схема
		|		|Т1 a Т2 | q20 Т3  | q30 Т4 w
2		1		1	2

описывает следующий «процесс вычисления». Начинает работу машина Т₂. Если она заканчивает работу в состоянии q₂₀ , то начинает работать машина Т₁, а по окончании работы Т₁ вновь «выполняет работу» машина Т₂. Если же машина Т₂ останавливается в некотором заключительном со-стоянии, отличном от q₂₀ , то работу продолжает машина Т₃. Если Т₃ при-

 

ходит в заключительное состояние q₃₀ , то начинает работу машина Т₁; ес-

 

ли же Т₃ заканчивает работу в некотором заключительном состоянии, от-личном от q₃₀ , то работу продолжает машина Т₄. Если машина Т₄ когда-

 

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

 

 

 

 

13 

5. Список используемой литературы:

1. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1
2. Фалевич Б.Я. Теория алгоритмов. – М.: ИНФРА-М, 2006. – с.324.
3. Фалина Н.М. Машина Тьюринга // Информатика. - №26. – 2005. – с.12-15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

14