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

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

Пусть D – область исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D → R.
Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный результат для всех d є D.
Определение 2 (А.Н. Колмогоров): Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 3 (А.А. Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Машина Тьюринга
Управляющее устройство
Лента
Считывающая и пишущая головка

Машина Тьюринга – это модель алгоритма, которая иллюстрирует процессы, происходящие при реализации алгоритма. Машина Тьюринга является гипотетической машиной. Ее составляют следующие компоненты:
Управляющее устройство
Лента
Считывающая и пишущая головка
• Управляющее устройство в каждый данный момент времени может находиться в одном и только одном состоянии из некоторого множества состояний.
Состояния обозначаются буквами так называемого внутреннего алфавита Q = {q0, q1, qm}.
Состояние q1 считают начальным состоянием, а состояние q0 – конечным (заключительным).
Во внутренний алфавит включают также символы сдвига : R – вправо, L – влево, E – на месте.

• Лента, разделенная на ячейки, потенциально бесконечная в обе стороны - имеется в виду, что в каждый момент времени лента содержит конечное число ячеек, но при необходимости число ячеек можно увеличивать.
В каждой ячейке может быть записан один и только один символ некоторого внешнего алфавита A= {a0, a1 … an}.
Символ a0 принято считать пустым символом. Он обозначает пустую ячейку.
По умолчанию, во всех ячейках, в которых НЕ ЗАПИСАНЫ символы a1, a2 ,…, an записан символ a0 .
В качестве внешнего алфавита мы будем рассматривать алфавит E = {0; 1}, где a0=0 соответствует пустому символу.

• Считывающая и пишущая головка, которая в каждый данный момент времени обозревает одну ячейку.
На рис. считывающая головка обозревает ячейку ленты, в которой
записан символ an . Управляющее устройство находится в состоянии q1 (начальном состоянии).
В зависимости от состояния управляющего устройства головка либо оставляет обозреваемый символ без изменения, либо записывает на его место любой другой символ внешнего алфавита, либо стирает обозреваемый символ.
Далее головка либо остается на месте, либо передвигается на одну ячейку вправо или влево, при этом управляющее устройство переходит в некоторое новое состояние (состояние может и не меняться).

Каждое перемещение головки и изменение состояния управляющего устройства можно определить командой, которая обычно записывается в виде:
q a q’ a’ D
где q и q’ ∈ Q
D∈ {R, L, E}
Команда q a q’ a’ D
расшифровывается так: если машина находится в состоянии q и считанный с ленты символ a, то машина переходит в состояние q’, печатает в текущей клетке символ a’ и затем выполняет одно из трех действий множества D.

В зависимости от того, какая была записана входная информация на ленте, имеем 2 возможности работы машины Тьюринга :
После конечного числа тактов машина Тьюринга останавливается (переходит в конечное состояние q0) и при этом на ленте выходит результирующая информация. Остановка машины происходит и в том случае, если для пары (qi, аi) функция перехода не определена. В этом случае говорят, что машина применима к начальной информации А и перерабатывает ее в результирующую информацию В.
Машина Тьюринга не останавливается. В этом случае говорят, что машина не применима к начальной информации А.

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила (команды).
Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Алан Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга.
Это предположение известно как тезис Черча–Тьюринга.

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

На машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен - машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму.
В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга.
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью (суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но, тем не менее, всегда конечна).

Вычислимые функции по Тьюрингу — это множество функций вида которые могут быть реализованы на машине Тьюринга.
Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможно ли написать алгоритм, вычисляющий эту функцию.
В качестве множества N обычно рассматривается множество слов в двоичном алфавите {0, 1} и к нему добавляется специальное значение «неопределённость» = , соответствующее случаю, когда алгоритм «зависает».

Важно отметить, что множество программ для исполнителя алгоритмов счётно.
Поэтому множество вычислимых функций не более чем счётно; в то время как множество функций вида несчётно, если N счётно.
Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций.
Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет.