Машина Тьюринга

Что это такое?

Машина Тьюринга - это универсальная учебная машина, созданная для уточнения понятия алгоритм.

Первым из всех ученых идею универсального исполнителя предложил Алан Тьюринг (1936г.). Для уточнения понятия алгоритма, им был разработан абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.

Структура машины Тьюринга

Машина Тьюринга состоит из:

- бесконечной в обе стороны ленты, разделенной на ячейки;

        - каретки (читающей и записывающей головки);

        - программируемого автомата.

Программируемый автомат управляет кареткой, посылая ей команды в соответствии с заложенной в него сменяемой программой. Лента выполняет роль внешней памяти компьютера, автомат — роль процессора, а каретка служит для ввода и вывода данных.

Программа для машины Тьюринга

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

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.

Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = {0, 1, а0}.

Непрерывную цепочку символов на ленте называют словом.

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

Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q={q1,q2...}. Одно из состояний - q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.

Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.

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

- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

- Передвигаться на одну ячейку влево или вправо. 

- Менять свое внутреннее состояние.

Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки ("←” — влево, "→” — вправо, "точка” — нет перемещения) и новое состояние автомата qk.

Например, команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.

Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

Тезис Чёрча-Тьюринга:

Т.о. можно дать формальное определение алгоритма по Тьюрингу. Машина Тьюринга - математический объект, и данное на ее основе определение алгоритма может использоваться для доказательства.

Примеры работы машины Тьюринга

Задача 1.¹

На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.

Чтобы решить задачу, нам нужно:

-определить алфавит  машины Тьюринга А,

- определить набор состояний Q,

- составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)

Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А={1,0,a0}.

Определим возможные состояния:

1. q1 - автомат ищет правый конец слова (числа) на ленте

2. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.

Напишем программу:

1 часть. q1 - автомат ищет правый конец слова (числа на ленте)

1)если в рабочей ячейке записано 0 - переместиться вправо

2)если в рабочей ячейке записано 1 - переместиться вправо

3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2

Составим таблицу переходов для q1 т.о.:

1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп

2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.

3) если в рабочей ячейке пробел, записать в нее 1 и стоп.

Добавим в нашу таблицу состояние q2:

Задача 2.

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.

Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

Задача 3.

Требуется заменить все символы # и $ на нули. В момент запуска головка находится над любой буквой слова.

Вопросы:¹

1. Что такое универсальный исполнитель?

2. Опишите устройство и систему программирования машины Тьюринга.

3. Что такое состояние машины Тьюринга?

4. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?

5. В чем особенность состояний q0 и q1 машины Тьюринга?

6. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?

7. Сформулируйте тезис Чёрча — Тьюринга.

Компьютерный практикум:

(Методические материалы И.Г. Семакина. Сетевой семинар «Преподавание профильного курса информатики»)

1. Дано целое число в троичной системе счисления;  нужно увеличить его на единицу.  Для реализации программы использовать  учебную модель машины Тьюринга.

2.  К данному троичному числу прибавить 2.

3.  Прибавление единицы для целых чисел в пятеричной системе счисления

4.  Составьте два варианта программы для машины Тьюринга, решающей следующую задачу: целое десятичное число нужно умножить на 10.  Головка автомата расположена: а) левее  числа на какой-то свободной ячейке; б) правее числа на какой-то свободной ячейке.

5. На ленте машины Тьюринга слева от головки автомата расположена группа подряд стоящих звездочек. Нужно стереть все звездочки и получить на ленте число, равное первоначальному количеству звездочек. Составить программу, реализовать ее на учебной модели машины Тьюринга. Протестировать программу.

Машина Тьюринга программа (К. Поляков)

  Дополнительный материал:

1. Тренажер для изучения работы машины: программа  (К. Поляков) (пароль к архиву kpolyakov.narod.ru)

2. Почему надо знать машину Тьюринга (www.ieee.ru)

3. Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru)

4. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машины Тьюринга и алгоритмы Маркова. Решение задач. М.: МГУ, 2006.

Использованная литература: