Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Алтайский государственный технический университет им. И.И.Ползунова

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

сергиевская

.pdf

Скачиваний:

Добавлен:

14.02.2015

Размер:

582.23 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 66

Операции с машинами Тьюринга.

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

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

Принцип двойственности.

Пусть Т – произвольная программа (машина Тьюринга). Обозначим Т* программу, которая получается из Т заменой (во всех командах) R на L и наоборот. Программа Т* называется двойственной к Т.

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

T: q1 0q0 0E .

q11q11R

Возможны три случая.

1.В начальный момент головка машины обозревает нуль. Машина

останавливается.

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

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

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

Впрограмме заменим символ R на L. Получим программу:

T: q1 0q0 0E .

q11q11L

Данная программа будет двойственной к предыдушей. Непосредственной

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

первый нуль.

Очевидно, что (Т*)*=Т, то есть понятие двойственности является взаимным.

Машины Тьюринга, соответствующие двойственным программам, будем называть

двойственными машинами Тьюринга.

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

...qi a1a2 ... ,

и машина Т в момент времени t переработает ее в конфигурацию

...c1c2 ...qics ....

В то же время, двойственная машина Т* конфигурацию

...a2qi a1...

(симметричную первой конфигурации относительно a1 ) в момент времени t

переработает в конфигурацию

...qics ...c2c1...,

симметричную второй конфигурации относительно c1 .

В Содержание.

Способы композиции машин Тьюринга.

1. Последовательное подключение одной машины Тьюринга к другой.

Пусть T0 и T1 – две машины Тьюринга над алфавитом {0,1}, множества состояний

машин не пересекаются. Перенумеруем 0,1,…,l-1 все команды с q0 программы T0 .

Пусть p(x) – предикат на множестве {0,1,…,l-1}. Последовательное подключение

T1 к T0 (относительно предиката			p(x)) – это	машина Тьюринга T , которая
получается		следующим образом. Первая половина таблицы для T совпадает с
таблицей T0		для тех клеток, в которых нет команды с q0 .
	Если p(n)=1, то в клетке n – команда q1 'aE ,			a – номер строки (0 или 1), где
находится клетка n, q1' – начальное состояние T1 .
	Если p(n)=0, то в клетке n – команда с q0 . Вторая половина таблицы Т
полностью совпадает с таблицей T1 .

		q1 … q j … qm	q1'… qj '… qm '
	0
	1
	В частном случае, если q0		– начальное	состояние машины T0 , а q1' –
начальное состояние T1 , заменим в программе T0				состояние q0 на состояние q1', и
полученную программу объединим с программой T1 . В результате мы получим
программу для машины T , которая является композицией машин T0 и T1 по паре
состояний ( q0 , q1').
2.		Итерация машины Тьюринга. Пусть T0 – машина Тьюринга над

алфавитом {0,1}. Перенумеруем 0,1,…,l-1 все команды с q0 программы T0 . Пусть

p(x) – предикат на множестве {0,1,…,l-1}. Итерация машины Тьюринга T0

относительно предиката p(x) – это машина Тьюринга Т, которая получается

следующим образом. Таблица Т совпадает с таблицей T0 для тех клеток, в которых нет команды не с q0 .

Если p(n)=1, то в клетке n – команда q1aE , a – номер строки, где находится

клетка n, q1 – начальное состояние T0 .

Если p(n)=0, то в клетке n – команда с q0 .

Действительно, имеет место итерация, т.е. многократная работа машины T0 . В частном случае, если q0 – заключительное состояние машины T0 , а q′ –

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

Отметим, что начальных и заключительных состояний может быть несколько.

В Содержание.

	Задачи.
	1.	По заданной машине Тьюринга T и начальной конфигурации K1 найти
заключительную конфигурацию:
	q 0q 1R								; K1			=1q1 013 .
1) T :		1		1					; K1			=1q1 013 .
	q11q01E
	q		0q			1R
		1		1
	q 1q					1L							3
2)	T :	1		2									3
2)	T :		0q0 0R								; K1 = q1101 .
	q2		0q0 0R
	q		1q				0R
		2		1
	q 0q						1R
		1		2
	q 1q			2		0L						2
3) T :		1		2								2
3) T :			0q01E							; K1 =10 1q11.
	q2		0q01E
	q		1q 1L
		2		1
	q		0q					0R
		1			2
	q 1q					1L						2	2
4)	T :	1		2								2	2
4)	T :		0q0 0E								; K1 =101		q11 .
	q2		0q0 0E
	q		1q			1R
		2		1

q11q21L

; K1

=10q1 01.

T :

0q01E

1q21R

6) T :

0q2 0L

; K1 =1 0q11.

1q01L

7) T :

0q01E

; K1 =1 q1

01 .

q 0q

T : q11q2 0R ; K1 =12 q1101.

0q 0R

q1 0q0 0E

q 1q

0q01R

; K1

9) T :

1q3 0L

=1 q11.

0q 1R

q31q1 0L

q1 0q0 0E

10)

0q01L

T :

1q3 0R

; K1 = q11 01.

q31q1 0R

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

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

	q				0q					0R
			1				1
	q			1q					1L				3
1) T :			1				2						3
1) T :						0q0 0E							; а) P =1 01; б) P =101.
	q2					0q0 0E
	q				1q				1R
			2				1
	q 0q									0R
2)			1					2
2)	T : q11q2 0R ; а) P =13 ; б) P =1021.
	q				1q 1R
			2				1
	q					0q				1L
			1					1
	q				1q			2		0L			2	2	2	2
3) T :			1					2					2	2	2	2
3) T :		q				0q				1L		; а) P =10 1		; б) P =1 0 1 .
		q		2		0q				1L
				2					1

	q21q01E
	q1 0q21R
	q 1q 0L
					1				1
4)
4)	T : q2 0q31R ; а) P =1031; б) P =[10]21.
	q					2	1q			3	0L
						2				3

	q3 0q1 0R

q1 0q21Rq11q21R

5) T : q2 0q3 0R ; а) P =12 ; б) P =1041.

q21q1 0Lq3 0q21E

q 1q 0L

3 0

3.Построить в алфавите {0,1} машину Тьюринга, обладающую свойствами:

1)машина имеет одно состояние, одну команду и применима к любому слову в алфавите {0,1};

2)машина имеет одно состояние, две команды, не применима ни к какому слову в алфавите {0,1}, и в процессе работы головка обозревает бесконечное множество ячеек;

3)машина имеет две команды, не применима ни к какому слову в алфавите {0,1}, и

впроцессе работы головка обозревает одну ячейку.

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

4. По словесному описанию машины Тьюринга построить ее программу (в алфавите {0,1}).

1)Начав работу с первой единицы массива из единиц, машина “сдвигает” его на две ячейки вправо, не изменяя остального содержимого ленты, и останавливается на последней единице перенесенного массива.

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

3)Машина начинает работу с самой левой непустой ячейки и отыскивает нуль, примыкающий с левой стороны к первому справа массиву из трех единиц, окаймленному нулями. Головка останавливается на первой единице найденного массива (если такой есть). Содержимое ленты не меняется.

4)Головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается влево до тех пор, пока не пройдет подряд пять нулей. Головка останавливается на первой ячейке слева за этими пятью нулями, напечатав в ней единицу. Остальное содержимое ленты не меняется.

5)При заданном n ≥1 головка машины, начав работу с произвольной ячейки и двигаясь вправо, записывает подряд 2n нулей и останавливается на последнем из них.

6)Головка машины, двигаясь вправо от какой-либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее семи единиц, стирает в нем первые семь единиц и останавливается на самой правой из ячеек, в которых были стерты единицы. Остальное содержимое ленты не меняется.

7)При заданном значении n головка машины из n записанных единиц оставляет на ленте n −2 единицы, так же записанных подряд, если n ≥ 2 , и работает вечно, если n = 0 или n =1.

8)Машина реализует алгоритм вычисления функции ϕ(n) = 0 , считая, что число n

представляется записанными подряд n единицами, и массив из n единиц уже найден.

9)Машина реализует алгоритм вычисления функции ϕ(n) =1, считая, что число n

представляется записанными подряд n единицами, и массив из n единиц уже найден.

10) Машина реализует алгоритм вычисления функции

1, если n делится на p,

f p (n) = 0, если n не делитсяна p.

Считается, что число n представляется записанными подряд n единицами, и массив из n единиц уже найден.

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

12)Показать, что для всякой машины Тьюринга существует эквивалентная ей машина, в программе которой отсутствует символ E.

5.Для машин Тьюринга из задачи 1 построить двойственные машины.

6. Построить композицию T1T2

машин Тьюринга T1 и T2 по паре состояний

( q10 , q21) и найти результат применения композиции T1T2 к слову P .

q11

q12

q21

q22

T :

q 0R

q 1L

, T :

q211L

q121L

q111R

q211R

q201E

а) P =101; б) P =13 .

q11

q12

q13

T1 :

q10 0L

q13 0R

q11 0R

q121E

q131L

q110R

T2 :

q21

q22

q221R

q20 0R

q221L

q21 0L

а) P =1201; б) P =14 .

q11

q12

q13

T1 :

q12 0R

q13 0L

q101L

q111R

q131R

T2 :

q21

q22

q23

q22 0L

q23 0R

q20 0R

q211L

q221R

q211L

а) P =13 ; б) P =1012 .

7. Найти результат применения итерации машины T по паре состояний ( q0 , q1 ) к слову P (заключительными состояниями являются q0 и q0′).

1)
T :		q1		q2	q3	q4	q5
T :	0	q0 0E	q4 0E		q5 0E	q31R	q01R
	1	q2 0R	q2 0R		q1 0R	-	-
а) P =13 ; б) P =101.
2)
T :		q1		q2	q3	q4	q5	q6
T :	0	q0′0R	q0′0R		q4 0R	q51L	q6 0L	q0 0R
	1	q2 0R	q3 0R		q31R	q41R	q51L	q61L
а) P =12 ; б) P =15 .

ВОтветы и указания.

ВСодержание.

Ответы и указания.

Глава 1. Высказывания, формулы, тавтологии. 2. 2), 5), 8), 10) – истинные высказывания. 1), 4), 7) – ложные высказывания. 3), 6) высказываниями не являются. 3. Обратите внимание, что 7) – составное высказывание. 5. Не являются тавтологиями: 2), 3), 5). Вернуться в Задачи.

Глава 3. Исчисление высказываний. 1. 1), 2), 5), 7), 8), 9) – формулы исчисления высказываний. 3), 4), 6), 10) формулами исчисления высказываний не являются. 2. 2). 3. 5) Применить лемму. 6), 7), 9) – применить результат 5). 8), 10), 11), 12) – применить результат 9). Вернуться в Задачи.

Глава 5. Предикаты. 1. 1){−2}. 3) {2}. 5) {(x, y) R2 x − y =1}. 7) R . 8) {(x, y) R2 x ≥ y2 }. 9) {1,2,3,5,7}. 10) {−1}. 2. 1), 3), 4), 6), 7), 9), 10). 1. 2), 5), 8). 0. 3.

7) Воспользоваться формулой A ↔ B = ¬A¬B AB . 4. 1) x t z(¬R(x, y, z) P(t, y)).

2) x t(¬R(x,t, z) P(x, y)). 3) t s(P(t, y) Q(x, s)). 4) x t(P(x,t) Q(x, y)). 5) t s z(¬R(x,t) P(s, y, z)).

6) t x y z(P(t, y) Q(x, z)). 7) x z(¬P(x, y) Q(x, z)).

8)x y z(P(x, y) ¬Q(x, z)).

9)s z t(¬P(s, y, z) R(x, y,t) Q(x, y)).

10)x t(¬P(x, y, z) Q(x, y,t)). 8. Можно привести такой пример: P(x) =" x = 0" , Q(x) =" x =1". Предикаты рассматриваются на множестве R . Вернуться в Задачи.

Глава 8. Рекурсивные функции. 1. 1) x . 2) x( y +1) .

			y
3)	x +			, y = 2k,		4) x2	y	. 5) x
	x +	2		, y = 2k,			y
	f (x, y) =	2

	y −1, y = 2k +1.
8)	1, y	=		2k,	9)			0,
8)	f (x, y) =			2k +1.	9)	f (x, y) =
	x, y	=		2k +1.				x,
10)	0, y = 0,					Вернуться в
10)	f (x, y) =			−1, y > 0.		Вернуться в
	x + y			−1, y > 0.

y . 6) sgn(x) . 7) x2 y .

y = 2k,

y = 2k +1.

Задачи.

Глава 9. Машины Тьюринга. 1. 1) 12 q013 . 2) q01013 . 3) 1q0101. 4) 1014 q0 0 . 5) 10q012 . 6) 12 q012 . 7) 120q012 . 8) 1204 q01. 9) q0 031021.

11)10q0 012 . 2. 1) а) T (P) =1301; б) T (P) =101. 2) а) Неприменима;

б) T (P) =1. 3) а); б) Неприменима. 4) а) T (P) =12013 ; б) Неприменима. 5) а)

Неприменима; б) T (P) =1. 6. 1) а) 1401; б) 15 . 2) а) 1201;

б) 1012 . 3) а) 14 ; б) 1201. 7. 1) а) 12 ; б) 1. 2) а)1; б) 1. Вернуться в Задачи.

В Содержание.

Литература.

1.Бочкарева О.В. Учебное пособие по математике (специальные главы). М., Радио и связь, 2001.

2.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М., Наука, 1992.

3.Горбатов В.А. Фундаментальные основы дискретной математики. М., Наука, 2000.

4.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М., Энергоатомиздат, 1988.

5.Кук Д., Бейз Г. Компьютерная математика. М., Наука,1990.

6.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., ФИЗМАТЛИТ, 2001.

7.Логинов Б.М. Введение в дискретную математику. Калуга, 1998.

8.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. СПб, Лань, 1999.

9.Математическая энциклопедия. Т. 1. М., Советская Энциклопедия, 1977.

10.Мендельсон Э. Введение в математическую логику. М., Наука, 1984. 11.Непейвода Н.Н. Прикладная логика. Новосибирск, Изд-во Новосибирского

университета, 2000.

12.Новиков Ф.А. Дискретная математика для программистов. СПб, Питер, 2000. 13.Тишин В.В. Теория алгоритмов, предикаты. Самара, 2001.

14.Фролов И.С. Элементы математической логики. Самара, Самарский университет, 2001.

15.Яблонский С.В. Введение в дискретную математику. М., Высшая школа, 2001.

В Содержание.

<<< < Предыдущая 1 2 3 4 56 / 66

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
14.02.20152.98 Mб48Сварка металлов.pdf
#
14.02.20158.26 Mб379сд.01_пиэ_о_проектирование ИС_12310-2010_8_1.doc
#
13.09.2019192.51 Кб2Себестоимость.doc
#
21.07.201932.03 Кб1семинар педагогика_15_12_11.docx
#
14.02.201550.35 Кб125Сензитивные периоды развития.docx
#
14.02.2015582.23 Кб33сергиевская.pdf
#
14.02.2015717.82 Кб19серегина.doc
#
12.03.2016125.95 Кб11Силлабус ЖБК.doc
#
14.02.201555.81 Кб23силлабус по логике.doc
#
09.11.2019125.95 Кб3Силлабусы по дисциплинам.doc
#
06.12.201836.48 Кб3СиМПД 12.12.11.docx