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

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

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

1 Лента (внешняя память) бесконечная в обе стороны полоска, разбитая на ячейки, перенумерованная целыми числами. В каждую ячейку в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = , где n . Наличие в ячейке символа , называемого пустым, означает, что данная ячейка пустая. В этом алфавите в виде слова − конечного упорядоченного набора букв − кодируется информация, которая подается в МТ. Машина перерабатывает входную информацию в новое слово (возможно, что оно совпадает с входным словом).

2. Считывающая головка, перемещающаяся вдоль ленты и обозревающая в каждый момент времени ровно одну ячейку. Головка может считывать содержимое ячейки и записывать в неё ровно один символ из алфавита А. За один такт (шаг) работы она, кроме этого, может сдвинуться на одну ячейку влево (Л), на одну ячейку вправо (П) либо сохранить своё положение (Н). Через D = {П, Л, Н} обозначим множество перемещений головки.

3. Память машины, представляющая собой некоторое конечное множество внутренних состояний Q = {q , q , q ,…,q }, Будем считать, что мощность . Два состояния машины имеют особое назначение: -начальное внутреннее состояние, -заключительное внутреннее состояние (стоп-состояние). Машина работает во времени, которое считается дискретным и его моменты занумерованы: 1, 2, 3, …. В каждый момент времени МТ характеризуется положением головки и внутренним состоянием. Например, под ячейкой, над которой находится головка, указывается внутреннее состояние машины.

		↓
	Λ			Λ			Λ

4. Устройство управления (УУ) в каждый момент времени t в зависимости от внутреннего состояния машины и считываемого в этот момент символа на ленте, над которым находится головка, выполняет действия, определяемые командой, которая записывается так:

, (1)

где

По этой команде УУ выполняет действия:

а) «считывает» символ и заменяет его символом (возможно, что );

b) перемещает головку в направлении ;

с) изменяет имеющееся в момент t внутреннее состояние на новое состояние , в котором будет машина в последующий момент времени t + 1 (возможно, что ).

В левой части команды (1) никогда не встречается .

Так как множества A и Q конечны, то команд вида (1), в которых левые части попарно различны, конечное число.

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

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

В начальный момент времени на ленте записано некоторое слово в алфавите = А-{ } = , остальные ячейки заполнены пустым символом. Исходное слово на ленте с начальным состоянием и положение головки над первым символом называется начальной конфигурацией. Исходное слово на ленте записано в ячейках, начиная с первой. Говорят, что МТ применима к слову начальной конфигурации, если при работе с этим словом через конечное число шагов выполняется команда, содержащее в правой части заключительное состояние , и работа над этим словом прекращается. То, что получилось при этом на ленте вместе с состоянием и положением головки, называют заключительной конфигурацией. В противном случае говорят, что МТ не применима к слову начальной конфигурации.

Пример 1. Построить машину Тьюринга, которая в алфавите слово «abb» преобразуют в слово «bba».

Решение. Составим программу МТ:

В результате работы МТ над словом «abb» будут выполнены следующие шаги:

	Λ	a	b	b	Λ		1-й шаг
							(начальная конфигурация)
		Λ	b	b	Λ		2-й шаг
		Λ	b	b	Λ		3-й шаг
		Λ	b	b	Λ		4-й шаг
		Λ	b	b	a		5-й шаг
							(заключительная конфигурация)

Работа МТ закончена.

Работу данной МТ можно интерпретировать следующим образом: она запоминает 1-ю букву исходного слова и при этом стирает его с ленты; головка движется вправо до первой пустой клетки, в которую и записывается первая исходная буква исходного слова.

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

	Λ	a	b

Пример 2. Построить машину Тьюринга, вычисляющую числовую функцию

Решение. Пусть внешним алфавитом данной МТ является множество . Число на ленте машины записывается в виде набора из х единиц :

						x-1	x
	Λ				…			Λ

Программа МТ выглядит следующим образом:

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

Работа МТ в алфавите , реализующая вычисление числовой функции , описывается следующей программой

	Λ

где любое натуральное число m кодируется набором из m+1 единиц.

Можно показать, что все арифметические функции натурального аргумента реализуемы МТ.

Данное утверждение может быть сформулировано более точно.

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

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

Дата добавления: 2015-08-18