Машина Тьюринга и алгоритмически неразрешимые проблемы

 

Q A	q1	q2	q3	q4	q5	q6	q7
a0	q4 a0П	q6a0П	q6a0П	q01	q4a0 П	q0a0	q6a0П
1	q21Л	q31Л	q11Л	q5 a0	q5a0	q7a0	q7a0

 

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

6)   1111 

Решение

						q1
			1	1	1	1

 

					q2
			1	1	1	1

 

				q3
			1	1	1	1

 

			q1
			1	1	1	1

 

		q2
		a0	1	1	1	1

 

			q6
		a0	1	1	1	1

 

			q7
		a0	a0	1	1	1

 

				q6
		a0	a0	1	1	1

 

				q7
		a0	a0	a0	1	1

 

					q6
		a0	a0	a0	1	1

 

					q7
		a0	a0	a0	a0	1

 

						q6
		a0	a0	a0	a0	1

 

 

						q7
		a0	a0	a0	a0	a0

 

							q6
		a0	a0	a0	a0	a0	a0

 

 

 

10 задание

Машина Тьюринга задается следующей функциональной схемой

 

Q А	q1	q2	q3
a0		q31П	q1a0Л
1	q2a0Л	q21Л	q31П
*	q0a0	q2*Л	q3*П

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

1. 1*111

Решение

1*111 1*11q11 1*1q21a0 1*q211a0 1q2*11a0 q21*11a0 q2a01*11a0 1q31*11a0 11q3*11a0 11*q311a0 11*1q31a0 11*11q3a0 11*1q11a0 11*q21a0a0 11q2*1a0a0

1q21*1a0a0 q211*1a0a0 q2a011*1a0a0 1q311*1a0a0 11q31*1a0a0 111q3*1a0a0

111*q31a0a0 111*1q3a0a0 111*q11a0a0 111q2*a0a0a0 11q21*a0a0a0 1q211*a0a0a0 q2111*a0a0a0 q2a0111*a0a0a0 1q3111* a0a0a0 11q311* a0a0a0 111q31* a0a0a0

1111q3*a0a0a0 1111*q3 a0a0a0 1111q1* a0a0a0 1111q0 a0a0a0a0 1111

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

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними: P<=NP<=EXPTIME

Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.

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

Если все задачи класса NP решаются за полиномиальное время и на детерминированной машине, то P=NP. Тем не менее, никем не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.

 

 

Список использованной литературы

 

неразрешимость

1. Гуц А.К. Математическая лоrика и теория алrоритмов. - Омск: Издательство Наследие. Диалог-Сибирь, 2003. - 108 с.

2. Игошин В.И. Задачи и  упражнения по математической логике и теории алгоритмов / В. И. Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.

3. Лавров И. А. Математическая логика : учеб. пособие для студ. высш. учеб. заведений / И.А.Лавров; под ред. Л.Л. Максимовой. — М.: Издательский центр «Академия», 2006. — 240 с.

4. Михайлов А,Б., Рыжова  Н.И., Швецкий М.В. Упражнения по  основам математической логики. Формальные системы первого порядка. Учебное пособие для студентов  математического факультета - Санкт-Петербург: РГПУ. 1997. - 127 с.

3. Рощин А.Г., Половов Р.М. Теория автоматов. Часть I. Тексты лекций – Москва: МГТУ ГА, 2001. – 76 с.

3. Фалина Н.М. Машина Тьюринга // Информатика. – №26. – 2005. – с.12-15

7. Фалевич Б.Я. Теория алгоритмов. – М.: ИНФРА-М, 2006. – с.324