Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 14 стр.

UptoLike

Составители: 

S = {R, L, E} - направления сдвига;
p
0
начальное состояние; p
0
Q;
p
z
заключительное состояние; p
z
Q;
a
0
символ для обозначения пустой ячейки, a
0
A;
a
1
специальный символ - разделитель цепочек на ленте, a
1
A.
Командой машины Тьюринга называется элемент функции переходов qa pbr, где q и
p Q; a и bA; rS. Каждая команда описывает один такт работы машины Тьюринга.
Конфигурация машины Тьюринга представляется следующим образом: t = <CqaB>, где
C - цепочка, находящаяся слева от считывающей головки;
q - состояние машины Тьюринга;
a - символ, находящийся под головкой машины Тьюринга;
B - цепочка, находящаяся справа от головки машины Тьюринга.
Конфигурация <CqaB> непосредственно переходит в конфигурацию <C
n
q
n
a
n
B
n
>, если
новая конфигурация получена в результате применения одной команды к исходной
конфигурации.
Обозначим непосредственный переход из одной конфигурации в другую следующим
образом: <CqaB><C
n
q
n
a
n
B
n
>.
Конфигурация, содержащая начальное состояние, называется начальной, а содержащая
заключительное состояние - заключительной. Если цепочка С в конфигурации пустая, то
начальная и заключительная конфигурации называются стандартными.
Машина Тьюринга перерабатывает цепочку x в цепочку y, если, действуя из начальной
конфигурации и имея на ленте цепочку x, машина Тьюринга переходит в заключительную
конфигурацию, имея на ленте цепочку y. Если начальная и заключительная конфигурации
являются стандартными, то процесс переработки x в y является правильной переработкой.
3.4. Способы представления машины Тьюринга
Существует три способа представления машины Тьюринга: совокупностью команд, в
виде графа, в виде таблицы соответствия.
3.4.1. Представление машины Тьюринга совокупностью команд
Совокупность всех команд, которые может выполнять машина, называется ее
программой.
Машина Тьюринга считается заданной, если заданы ее внешний и внутренний алфавиты,
программа, начальная конфигурация и указано, какие из символов обозначают пустую
ячейку и заключительное состояние.
Чтобы записать совокупность команд, нужно воспользоваться следующими правилами:
1) начальному шагу алгоритма ставится в соответствие q
0
- начальное состояние;
2) циклы реализуются так, что последнее действие цикла должно соответствовать
переходу в то состояние, которое соответствует началу цикла;
3) соседним шагам алгоритма соответствует переход в смежные состояния, которые
соответствуют этим пунктам;
4) последний шаг алгоритма вызывает переход в заключительное состояние.
В качестве примера рассмотрим совокупность команд машины Тьюринга, которая
инвертирует входную цепочку, записанную с использованием нулей и единиц.
Пусть алфавит машины Тьюринга задан множеством A={0, 1, ε}, где
символ ε соответствует пустой ячейке, а число состояний устройства управления задано в
виде множества Q = {q
0
, q
1
, q
z
}.
Если, например, начальная конфигурация имеет вид q
0
110011, то конечная
конфигурация после завершения операции инвертирования должна иметь вид q
z
001100. Для
решения задачи машиной будет порождена следующая последовательность команд: