15.Оценка вычислительной сложности. Машина Тьюринга. [ консп. 25 ]

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

Ее суть: математическая модель применяется для оценки вычислительной сложности. Тьюринг сформулировал следующие положения:

1. если задача решается на его модели, то это задача

вычислений

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

машина может иметь набор состояний а(альфа)0, а1 … аk

а0 – начальное. В ячейке может храниться буква алфавита {В(бета)0, В1, Вn} В0 – пустая ячейка. В ячейку может быть записана или считана буква алфавита. После этого действия УУ может дать команду на движение ленты вправо или влево на одну ячейку. Отдельный вход – остановка. В машине может быть реализована дополнительная головка с помощью которой информация может быть предварительно записана на ленту.

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

1. команды чтения и записи

2. команды переадресации

3. команды модификации содержимого ячейки на ленте

4. команды условного перехода

5. команды остановки

Пример:

Пусть на ленте записан набор из следующих символов {S0,S1,S2,S3}. Требуется провести сортировку по возрастанию.

Машина должна работать в соответствии со следующей таблицей состояний:

! – остановка

П – перемещение вправо

Л – перемещение влево

-- - запрещ. комбинация.

	a0	a1	a2	a3
S0	а0	а0	а0	--
	s0 П	s0 !	s0 !	--
S1	а1	а1	а1	--
	s1 П	s1 П	s1 Л	--
S2	а2	а2	а2	--
	s2 П	Заs2 П	s2 П	s1 Л
S3	а2	а2	а2	--
	s3 П	s3 П	s3 П	--

Зададим некоторую комбинацию на ленте:

s0

s1

s3

s2

s1

s3

s0

s0

такты

Вх

сост

Вых1

Вых2

s0

0

s0

а0

s0

П

s1

1

s1

а0

s1

П

s3

2

s3

а1

s2

П

s2

3

s2

а2

s2

П

s1

4

s1

а2

s2

Л

s0

s1

s2

s2

s1

s1

s3

s0

5

s2

а3

s1

Л

s2

s1

6

s2

а0

s2

П

s2

s1

7

s1

а2

s2

Л

s0

s1

s2

s2

s2

s1

s3

s0

8

s2

а3

s1

Л

s1

s1

9

s1

а0

s1

П

s1

s1

10

s1

а1

s1

П

s2

s2

s1

s3

s0

s0

11

s2

а1

s2

П

s2

12

s2

а2

s2

П

s3

13

s3

а1

s2

П

s0

s1

s1

s2

s2

s3

s0

s0

14

s0

а2

s0

!

Тьюринг строго доказал что любой конечный автомат может быть спроектирован с помощью его машины.

Предположим что мы имеем автомат Мили:

	а0	а1	а2	а3
x1	a1	a2	a3	a0
	y1 П	y2	y3	y0
x2	a0	a0	a0	a0
	y0	y0	y0	y0

<- везде добавить переход вправо

Правило, сформулированное Тьюрингом:

Для того чтобы машина Тьюринга работала в соответствии с таблицей Мили нужно выполнить следующие условия:

А) начать работу с некоторой ячейки а0 и заставить автомат Тьюринга перемещаться вправо т.е. добавить кругом перемещение вправо в таблицу состояний. Это является ключом для построения автомата Тьюринга.

• Остальные условия написаны неразборчиво.. =\