Описание машины Тьюринга совокупностью команд, таблицей соответствия и в виде графа

Описание машины Тьюринга

Машина Тьюринга представляет собой автомат, имеющий бесконечную в обе стороны ленту, считывающую головку и управляющее устройство. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной МТ. Каждое правило перехода предписывает МТ, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма. Таким образом, за 1 такт работы МТ может считать символ, записать вместо него новый или оставить его без изменения и сдвинуть головку на одну ячейку влево или вправо или оставить ее на месте.

Конкретная машина Тьюринга задается перечислением

- элементов множества букв алфавита A = {a₀, a₁, …, a_m}, где а₀ – символ пустой ячейки;

- элементов множества состояний Q = {q₀, q₁, ..., q_n}, где q₀ – состояние остановки: попав в него, машина прекращает работу; q₁ – начальное состояние: в этом состоянии машина начинает работать;

- набором правил, по которым работает машина. Правила имеют вид: q_ia_t→q_ja_pd_k(если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_t, то головка переходит в состояние q_j, в ячейку вместо a_t записывается a_p, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (H)).

Описание машины Тьюринга совокупностью команд, таблицей соответствия и в виде графа

Пример 3.1. Рассмотрим совокупность команд МТ, которая инвертирует входную цепочку, записанную с использованием нулей и единиц. Пусть алфавит МТ задан множеством A={0, 1, e}, где e соответствует пустой ячейке, а число состояний устройства управления задано в виде множества Q = {q₀, q₁, q_z}.

Если, например, начальная конфигурация имеет вид q₀110011, то конечная конфигурация после завершения операции инвертирования имеет вид q_z001100.

Идея решения. В стандартной начальной конфигурации головка стоит над первым символом слева, и УУ находится в начальном состоянии. На следующем такте МТ, не меняя своего состояния, заменяет символ 0 на 1 или 1 на 0 и сдвигается вправо на один символ. После просмотра всей цепочки под головкой оказывается символ, указывающий на пустую ячейку. В этом случае МТ переходит в новое состояние и сдвигается влево на один символ. На последующих тактах управляющее устройство не меняет своего состояния, оставляет без изменения символ под головкой и перемещается влево до тех пор, пока не встретит пустую ячейку. Встретив пустую ячейку, машина Тьюринга переходит в заключительное состояние и перемещается вправо на один символ, переходя в стандартную заключительную конфигурацию.

Для решения задачи МТ будет порождена следующей последовательностью команд:

q₀1 → q₀0R,

q₀0 → q₀1R,

q₁0 → q₁0L,

q₁1 → q₁1L,

q₀e → q₁eL,

q₁e → q_zeR.

МТ из рассмотренного примера инвертирования цепочки, состоящей из символов 0 и 1, будет представлена в виде графа следующим образом:

МТ из рассмотренного примера инвертирования цепочки, состоящей из символов 0 и 1, будет представлена таблицей соответствия следующим образом:

Контрольные вопросы (формализация понятия алгоритма)

1. В чем состоит содержание теоремы Тьюринга?

2. Каково устройство абстрактной машины Тьюринга? Каковы выполняемые ей действия? Охарактеризуйте машину Тьюринга. В чем отличие свойств МТ от реальной вычислительной машины.

3. Как описывается машина Тьюринга? Приведите примеры схем машин Тьюринга.

4. Какие операции существуют для машины Тьюринга?

5. Покажите на примере реализацию операций композиции и ветвления с помощью машины Тьюринга.

6. Какими свойствами обладает операция композиции?

7. Что такое конфигурации машины Тьюринга и какие виды конфигураций существуют? Что называется композицией машин Тьюринга?

8. Какие элементарные машины Тьюринга существуют? Охарактеризуйте каждую элементарную машину.

9. Постройте копирующую машину K_m с помощью остальных элементарных машин.

10. Постройте выбирающую машину T_m с помощью остальных элементарных машин.

11. Определите правильную вычислимость функции по Тьюрингу.

12. Докажите, что каждая элементарная функция правильно вычислима по Тьюрингу.

13. Докажите, что операции подстановки, примитивной рекурсии и минимизации сохраняют свойство правильной вычислимости функции по Тьюрингу.

14. Докажите, что всякая ПРФ, всякая ЧРФ – правильно вычислима по Тьюрингу.

15. Объясните эквивалентность двух уточнений алгоритма.

16. Чем отличаются уточнения понятия алгоритма в виде рекурсивной функции от машины Тьюринга?

Темы для рефератов (формализация понятия алгоритма)

1. Многоленточные и многоголовочные машины Тьюринга.

Темы семинарских занятий (формализация понятия алгоритма)

1. Формализация понятия алгоритма и алгоритмическая разрешимость.

2. Абстрактные автоматы. Уточнение понятия алгоритма. Машины Тьюринга.

Задачи и упражнения для выполнения на занятии (формализация понятия алгоритма)

1. Построить таблицу соответствия и функциональную схемы для машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111.

2. Построить таблицу соответствия и функциональную схемы для машины Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.

Оценить, как изменяется число тактов (по какому закону), совершаемых машиной при линейном увеличении размерности входного слова. В качестве примера взять пример из лекции (инвертирование битов) и Задание 1. (Следует показать, что время работы также возрастает линейно).

3. Постройте функциональные схемы для машины Тьюринга, вычисляющие простейшие арифметические операции (сложение, вычитание, умножение, деление) двух чисел.

4. Постройте программу для машины Тьюринга вычисляющую следующую функцию f(x) = x + 3.

5. Напишите программу для машины Тьюринга, производящую обращение функции.

6. Вычисляет ли функцию  машина Тьюринга в алфавите {L, 1} с программой в виде таблицы соответствия:

http://bsuir-helper.ru/predmet/ais/laby/laba-1-mashiny-tyuringa

Задачи и упражнения для выполнения дома (алгоритмы, свойства алгоритмов)

1. Построить таблицу соответствия и функциональную схему машины Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.

2. Построить таблицу соответствия и функциональную схему машины Тьюринга, распознающую слова, заканчивающиеся тремя подряд идущими единицами.

3. Построить таблицу соответствия и функциональную схему машины Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.

4.