Инф-ка_Л11-12_И_Данные_Код-е_Адекв

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

51

В1936 г. Аланом Тьюрингом для уточнения понятия

А был предложен абстрактный универсальный Исп-ль: логическая выч-я конструкция, а не реальная ВМ.

«Универсальный Исп-ль» может имитировать любого другого Исп-ля.

Например, операции, которые выполняют реальные

ВМ можно имитировать на универ-м Исп-ле.

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

52

•В состав машины Тьюринга входит бесконечная в обе стороны лента,

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

53

•УУ может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита.

Выделяется особый пустой символ,

заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные Данные.

54

•УУ работает согласно правилам перехода, которые представляют А, реализуемый данной МТ. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку А.

55

Основные части машины Тьюринга

qj УУ

Головка

		«»	a		aj	«»
				k	q
					m

Лента

56

Головка – писать, читать, стирать символ и перемещаться вдоль Ленты,

Q = { q1 … qn } – множ-во состояний Гол,

A = { a1 … am } – алфавит машины.

Конкретная машина Тьюринга при заданных элементах A, Q и множества

команд

57

•Конкретная МТ задаётся:

–множеством элементов букв алфавита A,

–множества состояний Q,

–набором правил, по которым работает машина.

Правила имеют вид:

qiaj→qi1aj1dk

(если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R),

остаться на месте (N)).

59

Для каждой возможной конфигурации

<qi, aj> имеется ровно одно правило.

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

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

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

60