Разработка машин Тьюринга

Пример №1 – Замена символа и перемещение головки.

А = {0,1,2,3,4,5,6,7,8,9}

Пусть Р не пустое слово поступающее на вход МТ. Необходимо получить число на 1 больше чем входное.

Действия:

1. Переместить головку к последней цифре числа;

2. Если эта цифра от 0 до 8, нужно заменить цифрой больше на 1 и остановиться;

3. Ели цифра 9 то заменить на 0 и переместиться к предыдущему разряду, т.е. сдвинуть ленту вправо. Повторяем действия 2 и 3.

4. Если считана пустая ячейка то число состояло из одних 9 и заменяем S₀ на 1 и стоп.

	0	1	2	3	4	5	6	7	8	9	S0
q0	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q1п
q1	q3 1С	q3 2С	q3 3С	q3 4С	q3 5С	q3 6С	q3 7С	q3 8С	q3 9С	q2 0П	-
q2	q3 1С	q3 2С	q3 3С	q3 4С	q3 5С	q3 6С	q3 7С	q3 8С	q3 9С	q2 0П	q3 1С
q4	q4 S0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q0Л	q3 1С

q₄ – добавляем что бы стирать незначащие нули.

q₀2345

q₀ 2→ q₀Л 2q₀345

q₀3→ q₀Л 23q₀45

q₀4→ q₀Л 234q₀5

q₀5→ q₀Л 2345q₀

q₀S₀→ q₁П 234q₁5

q₁5→ q₃6С 234q₃6

Пример №2 – Анализ символов.

Дан алфавит {a,b,c}, первый символ не пустого слова Р переместить в конец.

Действия:

1. Запоминаем первый символ и стираем его;

2. Перемещаемся в конец, на пустую ячейку;

3. Пишем запомненный символ.

Для запоминания символа используются состояния автомата, в данном случае: q1 = a, q2 = b, q3 = c.

	a	b	c	S0
q0	q1 S0Л	q2 S0Л	q3 S0Л	q4C
q1	q1Л	q1Л	q1Л	q4aC
q2	q2Л	q2Л	q2Л	q4bC
q3	q3Л	q3Л	q3Л	q4cC

q₀baca

q₀b→ q₂ S₀Л q₂aca

q₂a→ q₂Л aq₂ca

q₂c→ q₂Л acq₂a

q₂a→ q₂Л acaq₂

q₂ S₀→q₄bC acaq₄b

Пример №3 – Сравнение символов и стирание слова.

Дан алфавит {a,b,c}, если первый и последний символы не пустого слова Р одинаковы, то слова не менять, иначе – стереть.

Действия:

1. Запоминаем первый символ слова, не стирая его, перемещаемся в конец слова;

2. Если первый и последний символы совпадают то стоп;

3. Если не одинаковы заменяем S₀ и двигаемся вправо. Повторяем это действие пока не дойдем до S₀.

	a	b	c	S0
q0	q1Л	q2Л	q3Л	q8C
q1	q1Л	q1Л	q1Л	q4П
q2	q2Л	q2Л	q2Л	q5П
q3	q3Л	q3Л	q3Л	q6П
q4	q8C	q7 S0П	q7 S0П	-
q5	q7 S0П	q8 S0C	q7 S0П	-
q6	q7 S0П	q7 S0П	q8 S0C	-
q7	q7 S0П	q7 S0П	q7 S0П	q8C

q₀babc

q₀b→ q₂Л bq₂abc

q₂a→ q₂Л baq₂bc

q₂b→ q₂Л babq₂c

q₂c→ q₂Л babcq₂

q₂S₀→ q₅П babq₅c

q₅c→ q₇ S₀П baq₇b

q₇b→ q₇ S₀П bq₇a

q₇a→ q₇ S₀П q₇b

q₇b→ q₇ S₀П q₇S₀

q₇S₀→ q₈C q₈S₀

Пример №4 – Удаление символов.

Дан алфавит {a,b}, из входного слова Р удалить второй символ.

Действия:

1. Запомнить первый символ, стереть его и переместить ленту влево;

2. Записать запомненный символ во вторую ячейку, стоп.

	a	b	S0
q0	q1 S0Л	q2 S0Л	q3C
q1	q3aC	q3aC	q3aC
q2	q3bC	q3bC	q3bC

q₀bab

q₀b→ q₂ S₀Л q₂ab

q₂ a→ q₃bC q₃bb

Пример №5 – Сжатие слова.

Дан алфавит {a,b,с}, из входного слова Р удалить первое вхождение символа а.

Действия:

1. Анализируем первый символ, если это а→S₀ и стоп. Если это b или c запоминаем его и стираем, переходим в соответствующее состояние;

2. Анализируем следующий символ если, а то вместо него пишем b или c и стоп. Если другой запоминаем и пишем предыдущий запомненный символ.

	a	b	c	S0
q0	q3 S0C	q1 S0Л	q2 S0Л	q3C
q1	q3bC	q1bЛ	q2bЛ	q3bC
q2	q3cC	q1сЛ	q3сЛ	q3cC

q₀baac

q₀b→ q₁ S₀Л q₁aac

q₁ a→ q₃bC q₃bac

Пример №6 – Вставка символа в слово.

Дан алфавит {a,b,с}, если входное слово Р не пустое, то после его первого символа вставить символ а.

Действия:

1. Анализируем первый символ и запоминаем его, записываем вместо него а, возвращаемся на одну позицию назад.

2. В пустую ячейку записываем запомненный символ и стоп.

	a	b	c	S0
q0	q1 аП	q2 аП	q3 аП	q4C
q1	-	-	-	q4aC
q2	-	-	-	q4bC
q3	-	-	-	q4cC

q₀bbac

q₀b→ q₂ aП q₂S₀abac

q₂ S₀→ q₄bC q₄babac

Пример №7 – Раздвижка слова.

Входной алфавит {a,b,c} в слово Р вставить а после первого вхождения символа с.

Действия:

1. Перемещаем ленту влево пока не встретим символ с;

2. Вместо с записываем а, перемещаемся вправо;

3. Запоминаем символ ячейки, записываем с, сдвигаемся вправо. Повторяем пока не дойдем до S₀, вместо которого пишем запомненный символ и стоп.

	a	b	c	S0
q0	q0Л	q0Л	q1 аП	q4C
q1	q2 cП	q3 cП	-	q4cC
q2	q2П	q3 аП	-	q4aC
q3	q2 bП	q3П	-	q4bC

q₀abac

q₀a→ q₀Л aq₀bac

q₀b→ q₀Л abq₀ac

q₀a→ q₀Л abaq₀c

q₀c→ q₁аП abq₁aa

q₁a→ q₂cП aq₂bca

q₂b→ q₃аП q₃aaca

q₃a→ q₂bП q₂S₀baca

q₂S₀→ q₄aC q₄abaca

Пример №8 – Формирование слова на новом месте.

Дан алфавит {a,b,c}, удалить из входного слова Р все символы а.

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

Действия:

1. Перемещаемся в конец слова и добавляем туда символ =;

2. Возвращаемся к началу слова;

3. Запоминаем первый символ и удаляем его, если это был символ а, то переходим к следующему символу. Если это другой символ, то перемещаемся в конец слова, где записываем запомненный символ;

Действия 2 и 3 повторяем до тех пор пока первым символом слова не окажется знак =, удаляем его и останавливаем МТ.

	a	b	c	S0	=
q0	q0Л	q0Л	q0Л	q1=П	-
q1	q1П	q1П	q1П	q2Л	q1П
q2	q2S0Л	q3S0Л	q4S0Л	-	q5S0C
q3	q3Л	q3Л	q3Л	q1bП	q3Л
q4	q4Л	q4Л	q4Л	q1cП	q4Л

q₀cba

q₀c→ q₀Л c q₀ba

q₀b→ q₀Л cb q₀a

q₀a→ q₀Л cba q₀

q₀S₀→ q₁=П cb q₁a=

q₁a→ q₁П c q₁ba=

q₁b→ q₁П q₁cba=

q₁c→ q₁П q₁S₀cba=

q₁S₀→ q₂Л q₂cba=

q₂c→ q₄S₀Л q₄ba=

q₄b→ q₄Л b q₄a=

q₄a→ q₄Л ba q₄=

q₄=→ q₄Л ba= q₄

q₄S₀→ q₁cП ba q₁=c

q₁=→ q₁П b q₁a=c

q₁a→ q₁П q₁ba=c

q₁b→ q₁П q₁S₀ba=c

q₁S₀→ q₂Л q₂ba=c

q₂b→ q₃S₀Л q₃a=c

q₃a→ q₃Л a q₃=c

q₃=→ q₃Л a= q₃c

q₃c→ q₃Л a=c q₃

q₃S₀→ q₁bП a= q₁cb

q₁c→ q₁П a q₁=cb

q₁=→ q₁П q₁a=cb

q₁a→ q₁П q₁S₀a=cb

q₁S₀→ q₂Л q₂a=cb

q₂a→ q₂S₀Л q₂=cb

q₂=→ q₅S₀C q₅S₀cb

Пример №9 – Фиксирование места на ленте.

Входной алфавит {a,b} удвоить входное слово Р, поставить между ним и его копией =.

Для фиксирования позиции в которую необходимо вернуться используется метод замены считаного символа его дубликатом: а→А, b→B.

Действия:

1. В конец слова записываем =4;

2. Возвращаемся к первому символу входного слова;

3. Если первый символ а заменяем на А и двигаемся в конец слова, где записываем копию а. тоже самое делаем с символом b.

4. Возвращаемся к первому не прочитанному символу, заменяя дубликат на исходный символ.

Действия 3 и 4 повторяем до тех пор пока не скопированы все символы.

	a	b	А	В	S0	=
q0	q0Л	q0Л	-	-	q1=П	-
q1	q1П	q1П	q2aЛ	q2bЛ	q2Л	q1П
q2	q3AЛ	q4BЛ	-	-	-	q5C
q3	q3Л	q3Л	-	-	q1aП	q3Л
q4	q4Л	q4Л	-	-	q1bП	q4Л

q₀ba

q₀b→ q₀Л bq₀a

q₀a→ q₀Л baq₀

q₀S₀→ q₁=П bq₁a=

q₁a→ q₁П q₁ba=

q₁b→ q₁П q₁S₀ba=

q₁ S₀→ q₂Л q₂ba=

q₂b→ q₄BЛ Bq₄a=

q₄a→ q₄Л Baq₄=

q₄=→ q₄Л Ba=q₄

q₄S₀→ q₁bП Baq₁=b

q₁=→ q₁П Bq₁a=b

q₁a→ q₁П q₁Ba=b

q₁B→ q₂ bЛ bq₂a=b

q₂a→ q₃AЛ bAq₃=b

q₃=→ q₃Л bA=q₃b

q₃b→ q₃Л bA=bq₃

q₃S₀→ q₁аП bA=q₁ba

q₁b→ q₁П bAq₁=ba

q₁=→ q₁П bq₁A=ba

q₁A→q₂aЛ baq₂=ba

q₂=→q₅C baq₅=ba

Машина Тьюринга с двумя выходами

Рассмотрим устройство МТ добавив в устройство управления машиной некоторое состояние При этом -конечное, тогда МТ переходит весли оно принимает слово х и запрещает-MT с двумя выходами

Определить имеется ли во входном слове подслово System

System

	S	Y	T	E	M		др
		Л	Л	Л	Л	С	Л
	Л		Л	Л	Л	C	Л
	Л
		Л	Л
				Л
					С

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

Схема машины:

▼

Устройство управления машины в каждый момент времени находится в одном из состояний множества q. Конфигурация машины считается заданной, если известно начальное состояние, входные слова каждой из лент и указана какая из ячеек каждой ленты считывается в данный момент конфигурация машины задается последовательно, где n-количество лент

... …

... …

…

... …