Формальное определение машины Тьюринга

Алфавит A – это некоторое конечное множество символов.

Цепочкой над алфавитом называется последовательность символов из того алфавита. Длина цепочки x представляет собой число символов в цепочке и обозначается | x |. Длина пустой цепочки равна нулю.

Конкатенацией цепочек X и Y называют цепочку, полученную приписыванием символов цепочки Y справа к цепочке X.

Машиной Тьюринга называется семерка вида T = (Q, A, δ, p₀, p_z, a₀, a₁), где Q – конечное множество состояний, в которых может находиться управляющее устройство;

A – входной алфавит;

δ – функция переходов, δ = Q . A → Q . A . S, где

S = {R, L, E} - направления сдвига;

p0 – начальное состояние; p₀ Î Q;

p_z – заключительное состояние; p_z Î Q;

a₀ – символ для обозначения пустой ячейки, a₀ Î A;

a₁ – специальный символ - разделитель цепочек на ленте, a₁ Î A.

Командой машины Тьюринга называется элемент функции переходов qa → pbr, где q и pÎ Q; a и bÎA; rÎS. Каждая команда описывает один такт работы машины Тьюринга.

Конфигурация машины Тьюринга представляется следующим образом: t = <CqaB>, где C - цепочка, находящаяся слева от считывающей головки;

q - состояние машины Тьюринга;

a - символ, находящийся под головкой машины Тьюринга;

B - цепочка, находящаяся справа от головки машины Тьюринга.

Конфигурация <CqaB> непосредственно переходит в конфигурацию <C_nq_na_nB_n>, если новая конфигурация получена в результате применения одной команды к исходной конфигурации.

Обозначим непосредственный переход из одной конфигурации в другую следующим образом: <CqaB>Þ<C_nq_na_nB_n>.

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

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

Дата добавления: 2015-07-26; просмотров: 158; Нарушение авторских прав

Мы поможем в написании ваших работ!