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

    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. Для
решения задачи машиной будет порождена следующая последовательность команд: