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

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

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

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

 

 

 

 

 

 

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

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

 

Тема:

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

 

 

 

 

Выполнил:

  студент группы 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₁ обо-

 

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