ВУЗ:
Составители:
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 и b∈A; r∈S. Каждая команда описывает один такт работы машины Тьюринга.
Конфигурация машины Тьюринга представляется следующим образом: 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. Для
решения задачи машиной будет порождена следующая последовательность команд:
S = {R, L, E} - направления сдвига; p0 – начальное состояние; p0 ∈ Q; pz – заключительное состояние; pz ∈ Q; a0 – символ для обозначения пустой ячейки, a0 ∈ A; a1 – специальный символ - разделитель цепочек на ленте, a1 ∈ A. Командой машины Тьюринга называется элемент функции переходов qa → pbr, где q и p∈ Q; a и b∈A; r∈S. Каждая команда описывает один такт работы машины Тьюринга. Конфигурация машины Тьюринга представляется следующим образом: t =, где C - цепочка, находящаяся слева от считывающей головки; q - состояние машины Тьюринга; a - символ, находящийся под головкой машины Тьюринга; B - цепочка, находящаяся справа от головки машины Тьюринга. Конфигурация непосредственно переходит в конфигурацию , если новая конфигурация получена в результате применения одной команды к исходной конфигурации. Обозначим непосредственный переход из одной конфигурации в другую следующим образом: ⇒ . Конфигурация, содержащая начальное состояние, называется начальной, а содержащая заключительное состояние - заключительной. Если цепочка С в конфигурации пустая, то начальная и заключительная конфигурации называются стандартными. Машина Тьюринга перерабатывает цепочку x в цепочку y, если, действуя из начальной конфигурации и имея на ленте цепочку x, машина Тьюринга переходит в заключительную конфигурацию, имея на ленте цепочку y. Если начальная и заключительная конфигурации являются стандартными, то процесс переработки x в y является правильной переработкой. 3.4. Способы представления машины Тьюринга Существует три способа представления машины Тьюринга: совокупностью команд, в виде графа, в виде таблицы соответствия. 3.4.1. Представление машины Тьюринга совокупностью команд Совокупность всех команд, которые может выполнять машина, называется ее программой. Машина Тьюринга считается заданной, если заданы ее внешний и внутренний алфавиты, программа, начальная конфигурация и указано, какие из символов обозначают пустую ячейку и заключительное состояние. Чтобы записать совокупность команд, нужно воспользоваться следующими правилами: 1) начальному шагу алгоритма ставится в соответствие q 0 - начальное состояние; 2) циклы реализуются так, что последнее действие цикла должно соответствовать переходу в то состояние, которое соответствует началу цикла; 3) соседним шагам алгоритма соответствует переход в смежные состояния, которые соответствуют этим пунктам; 4) последний шаг алгоритма вызывает переход в заключительное состояние. В качестве примера рассмотрим совокупность команд машины Тьюринга, которая инвертирует входную цепочку, записанную с использованием нулей и единиц. Пусть алфавит машины Тьюринга задан множеством A={0, 1, ε}, где символ ε соответствует пустой ячейке, а число состояний устройства управления задано в виде множества Q = {q0, q1, qz}. Если, например, начальная конфигурация имеет вид q0110011, то конечная конфигурация после завершения операции инвертирования должна иметь вид qz001100. Для решения задачи машиной будет порождена следующая последовательность команд:
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »