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

Определение алгоритма

Тема 4. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

Цели и задачи изучения темы:В данной теме изучаются основы работы машины Тьюринга.

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

Отметим важнейшие черты (свойства) алгоритма:

Массовость — применимость алгоритма не к одной задаче, а к классу задач.

Дискретность — четкая разбивка на отдельные этапы (шаги) алгоритма.

Детерминированность — такая организация этапов выполнения, при которой всегда ясно как осуществить переход от одного этапа к другому.

Конечность — для получения результата при применении алгоритма к решению конкретной задачи выполняется конечная последовательность шагов алгоритма:

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

Попытки формализовать понятие алгоритма привели к созданию машины Тьюринга, как некоего воображаемого устройства, реализующего алгоритм. Ещё одним шагом в определении понятия алгоритма стало появлениерекурсивных функций, как функций, формализующих понятие алгоритма и реализующих интуитивное понятие вычислимости. Вскоре было установлено, что множество рекурсивных функций совпадает с множеством функций, вычислимых на машинах Тьюринга. Появлявшиеся затем новые понятия, претендующие на объяснение понятия алгоритма, оказывались эквивалентными функциям, вычислимым на машинах Тьюринга, а значит, и рекурсивным функциям. Итогом развернувшейся дискуссии о том, что такое алгоритм, стало утверждение, называемое сейчас тезисом Чёрча.

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

Лента разбита на ячейки. Во всякой ячейке в точности один символ извнешнего алфавита A={a₀,a₁,...,a_n}. Некоторый символ (будем обозначать его А) алфавита А называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны

Управляющее устройство в каждый момент времени находится в некотором состоянии q_j, принадлежащем множеству Q= {q₀,q₁, ,q_m} (m=1) Множество Q называетсявнутренним алфавитом. Одно из таких состояний (обычно q₀) называется заключительным, а некоторое другое (обычно q_i) -начальным.

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

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

Конфигурацией на ленте (или машинным словом)называется совокупность, образованная:

1. Последовательностью a _i(1), a _i(2),…,a _i(s) символов из внешнего алфавита А, записанных в ячейках ленты, где a_i(1).- символ записанный в первой ячейке слева и т.д. (любая такая последовательность называется словом),

2. состоянием внутренней памяти q_r;

3. номером k воспринимаемой ячейки. Конфигурацию машины будем записывать так:

^ai(l),^ai(2),…^ai(r-l) ^ai(r)^а i(r+l), ^а i(r+2), …^ai(s)

q_r

здесь r-воспринимаемая ячейка, выделяется в виде дроби.

Если машина, находясь во внутреннем состоянии q_i, воспринимает ячейку с символом аu , записывает к следующему моменту времени в эту ячейку символ аг , переходит во внутреннее состояние q_s и сдвигается по ленте, то говорят, что машина выполняет команду q_ia_u šq_sa_rS , где символ S может принять одно из значений: -1 - сдвиг головки влево; +1 - сдвиг головки вправо; 0 - головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении строки а_u и столбца q_i будет стоять q_sa_rS ( см. таб.4.1.1)

Таб.6.2.1.

Если в программе машины для пары (q_i,a_u) пятерка отсутствует, то в таблице на пересечении строки a_u, и столбца q _i ставится прочерк.

Итак,машина Тьюринга есть, по определению, набор M=(A,Q,II), где А — внешний алфавит, Q — алфавит внутренних состояний,П — программа.

Если машина, начав работу с некоторым словом Р, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.

Пример 4.1.1. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=||.).

Решение. Рассмотрим алфавит А = {|, +, ^}. Машина определяется следующей программой:

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.

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

Решение. Искомую машину построим в алфавите А={|, a, ^}. Программа такой машины может выглядеть так:

Применим полученную машину к слову І І

Введение новой буквы и замена исходных | на a позволяет различить исходные | и новые (приписанные) |. Состояние q₁ обеспечивает замену | на a, состояние q₂ обеспечивает поиск a, предназначенных для замены на |, и останов машины в случае, когда a не обнаружено, q₃ обеспечивает дописывание | в случае, когда произошла замена a на |.