Введение в схемы, автоматы и алгоритмы

Тьюрингово программирование


В этом разделе мы приведем примеры вычислений на машинах Тьюринга и рассмотрим некоторые общие приемы, позволяющие комбинировать программы различных м. Т. для получения более сложных вычислений. Будем считать, что ячейки ленты м.Т. занумерованы от -? до +? , причем в начальной конфигурации головка находится в 1-ой ячейке:


Рис. 9.2.  Нумерация ячеек ленты машины Тьюринга

Пример 9.2.Функция f(x)=x+1

  • Унарное кодирование.

    Пусть м.Т.

    где P1: q0 |
    q0 | П, q0
    qf | Н.

  • Ясно, что м.Т.
    проходит по массиву палочек слева направо и записывает в первой пустой ячейке новую |.
  • Бинарное кодирование.

    Пусть м.Т.

    где

    Нетрудно видеть, что эта машина в состоянии q0 находит младший разряд двоичного входа, затем в состоянии q1, идя справа налево, заменяет единицы на нули до тех пор, пока не находит 0 (или

    ) и заменяет его на 1. Следовательно, м.Т.
    вычисляет функцию f(x) = x+1.

Пример 9.2. Копирование.

Рассмотрим функцию копирования (дублирования) слов в алфавите ?: copy(x)= x*x (мы предполагаем, что *

?).

Для ее реализации используем один из типичных приемов Тьюрингова программирования - { it расширение алфавита}.Пусть ?'= {a' | a

? } и ?1=?
?'. М.Т.
копирующая вход, работает следующим образом:

  1. отмечает 1-ый символ входа, идет направо, ставит * после входа и возвращается в начало:
  2. в состоянии qa движется направо и записывает a в первую свободную ячейку:
  3. возвращается в отмеченную ячейку и передвигает метку ' на одну ячейку вправо, снова переходя в состояние q2:
  4. увидев символ * в состоянии q5, останавливается:

Из этого описания непосредственно следует, что

для любого x
{?}*.



Содержание раздела