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

Московский  Авиационный Институт

(Государственный  Технический Университет)

Кафедра Прикладной Информатики

 

 

 

 

 

 

Реферат по курсу

Математическая  логика и теория алгоритмов

 

Тема:

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

 

 

 

 

Выполнил:

  студент группы 06-421

Иванников Н.Д.

 

 

Проверил:

Преподаватель каф. 609

Махорин А. О.

 

 

 

 

 

 

Москва, 2013 г.

 

СОДЕРЖАНИЕ

 

 

 

1. Математическая модель машины Тьюринга 3

 

2. Работа машины Тьюринга 6

 

3. Примеры машин Тьюринга, работающих в алфавите {a, b} 7

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

1. Математическая  модель машины Тьюринга

 

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

 

Машина Тьюринга (МТ) – это математическая модель идеализированной цифровой вычислительной машины.

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

 

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

 

1. Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, … . В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = {L, a₁, a₂ ,..., a_n-1 }, n ³ 2 . Пустая ячейка обозначается символом L, а сам символ L называется пустым, при этом остальные символы называются непустыми. В этом алфавите A в виде слова (конечного упорядоченного набора символов) кодируется та информация, которая подается в МТ. Машина «перерабатывает» информацию, поданную в виде слова, в новое слово.

 

2. Считывающая головка (некоторый считывающий элемент) пере-мещается вдоль ленты так, что в каждый момент времени она обозревает

3

 

ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оста-ваться на месте (Н). Обозначим множество перемещений (сдвига) головки D = {П, Л, Н}. Если в данный момент времени t головка находится в крайней клетке и сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка, над которой окажется головка в момент t + 1.

 

3. Внутренняя память машины представляет собой некоторое конеч-ное множество внутренних состояний Q = { q₀ , q₁, q₂ , ..., q_m }, m ³ 1. Будем считать, что мощность |Q | ³ 2. Два состояния машины имеют особое значение: q₁ – начальное внутреннее состояние (начальных внутренних состояний может быть несколько), q₀ – заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоя-нием. Например, под ячейкой, над которой находится головка, указывается внутреннее состояние машины.

 

 

¯

 

	a2	a1	L	a2	a3
	q1

 

 

4. Устройство управления в каждый момент t в зависимости от счи-тываемого в этот момент символа на ленте и внутреннего состояния ма-шины выполняет следующие действия: 1) изменяет считываемый в момент t символ a_i на новый символ a _j (в частности оставляет его без изменений,

 

т. е. a_i = a _j ); 2) передвигает головку в одном из следующих направлений:

 

Н, Л, П; 3) изменяет имеющееся в момент t внутреннее состояние машины

 

4

 

q_i  на новое q _j , в котором будет машина в момент времени t +1 (может

 

быть, что q_i  = q _j ).

 

Такие действия устройства управления называют командой, которую можно записать в виде:

 

qi ai ® a j  D q j ,

(1)

где q_i – внутреннее состояние машины в данный момент; a_i – считываемый в этот момент символ; a _j – символ, на который изменяется символ a_i (может быть a_i = a _j ); символ D есть или Н, или Л, или П и указывает направление движения головки; q _j – внутреннее состояние машины в следующий момент (может быть q_i = q _j ). Выражения q_i a_i и a _j D q _j называются левой и правой частями этой команды соответственно. Число команд, в которых левые части попарно различ-ны, является конечным числом, так как множества Q \ {q₀ } и A конечны.

 

Не существует команд с одинаковыми левыми частями, т. е. если про-грамма машины T содержит выражения q_i a_i ® a _j D q _j и q_t a_t ® a_k D q_k ,

 

то q_i ¹ q_t или a_i ¹ a_t и D Î{П, Л , Н}.

 

Совокупность  всех команд называется программой машины Тьюринга. Максимальное число команд в программе равно (n + 1) × m , где n + 1 = A и m + 1 = Q . Считается, что заключительное состояние команды

q₀ может стоять только в правой части команды, начальное состояние q₁

 

может стоять как  в левой так и в правой части команды.

 

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

 

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

 

5

 

2. Работа машины  Тьюринга

 

 

Работа машины полностью определяется заданием в  первый (на-чальный) момент: 1) слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); 2) положения головки; 3) внутреннего со-стояния машины. Совокупность этих трех условий (в данный момент) на-зывается конфигурацией (в данный момент). Обычно в начальный момент внутренним состоянием машины является q₁, а головка находится либо над первой слева, либо над первой справа клеткой ленты.

 

Заданное слово  на ленте с начальным состоянием q₁ и положение головки над первым словом называется начальной конфигурацией. В противном случае говорят, что машина Тьюринга не применима к слову начальной конфигурации.

 

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

 

Например, если в начальный момент на ленте записано слово a₁La₂ a₁a₁ , то начальная конфигурация будет иметь вид:

 

	a1	a2	L	a1	a1
	q1

 

(под клеткой, над которой находится головка, указывается внутреннее со-стояние машины).

 

6

 

Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применится команда с левой частью q₁a₁ .

 

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

 

Если в работе машины Тьюринга в некоторый момент t выполняется команда, правая часть которой содержит q₀ , то в такой момент работа маши-

ны считается  законченной, и говорят, что машина применима к слову на лен-те в начальной конфигурации. В самом деле, q₀ не встречается в левой части ни одной команды – этим и объясняется название q₀ «заключительное со-

 

стояние». Результатом работы машины в таком случае считается слово, кото-рое будет записано на ленте в заключительной конфигурации, т. е. в конфи-гурации, в которой внутреннее состояние машины есть q₀ . Если же в работе

 

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

 

3. Примеры машин  Тьюринга , работающих в алфавите {a, b}

 

Проиллюстрируем работу машину Тьюринга на следующем  примере.

 

Пример 1. Построить  машину Тьюринга T₁, которая применима ко всем словам с внешним алфавитом {a,b} и делает следующее: любое слово x₁x₂...x_n , где x_i = a или x_i = b (i =1,2,...n) преобразует в слово x₂...x_n x₁,

 

т. е., начиная работать при слове x₁x₂...x_n  на ленте в начальной конфигу-

 

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

 

7

 

Решение. За внешний алфавит машины T₁ возьмем множество A = {L,a,b}, а за внутренний – Q = {q₀ ,q₁,q₂ ,q₃}. Команды определим сле-дующим образом: q₁a ® LПq₂ , q₁b ® LПq₃ , q_i y ® yПП_i , где y Î{a,b}, i = 2,3 ; q₂ L ® aHq₀ , q₃ L ® bHq₀ .

 

Рассмотрим работу машины T₁ над словом ba . В работе машины над словом ba начальная конфигурация имеет следующий вид:

 

¯

 

(1)		b	a

q₁

 

На первом шаге действует команда: q₁b ® LПq₃ . В результате создается следующая конфигурация:

 

			¯
(2)
		L		a
				q3
На втором шаге действует команда			q3 a ® aПП3 , и на машине создается
конфигурация
					¯
(3)
		L		a	L
					q3

 

Наконец, третий шаг обусловлен командой q₃L ® bHq₀ . В результате чего создается конфигурация:

 

¯

 

(4)		L	a	b

^q0

 

 

8

 

Эта конфигурация является заключительной, так как машина оказалась в состоянии остановки q₀ .

 

Таким образом, слово ba переработано в слово ab .

 

Полученную последовательность конфигураций можно записать более  коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите A È Q : q₁ba (содержимое обозреваемой ячейки записано справа от состояния, в котором находится данный момент машина). Далее, конфигура-ция (2) записывается так: q₃a , конфигурация (3) – aq₃L , и наконец, (4) – abq₀ .

 

Вся последовательность записывается так: q₁ba Þ Lq₃a Þ aq₃L Þ abq₀ .

 

Пример 2. Применить  машину Тьюринга T₁ из примера 1 к слову bbabb, исходя из начального положения, при котором в состоянии q₁ обо-

 

зревается крайняя  левая ячейка, в котором содержится символ этого слова.

 

 

 

Решение

 

 

 

(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