Вычислимость. Эквивалентность алгоритмических моделей

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

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

Головка машины Тьюринга может находиться в одном из состояний q₀, ..., q_m, одно из которых помечено как начальное. Набор состояний образует некоторый алфавит внутренних состояний Q машины Тьюринга M. Находясь в состоянии q_i, машина Тьюринга может выполнять следующие операции:

• считывать из клетки значение a_k;
• в соответствии с инструкцией записать в клетку другой символ a_l (возможно – тот же самый);
• перейти в другое состояние q_j (возможно – в то же самое);
• сдвинуться на одну клетку влево (d = L), вправо (d = R) или остаться в той же клетке (d = S).

Алгоритм работы машины Тьюринга можно записать в виде конечной последовательности «пятерок» вида q_i, a_k → q_j, a_l, d.

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

Результатом работы машины Тьюринга может быть:

• результативная остановка (машина нашла инструкцию d = S и остановилась в той же клетке);
• безрезультативная остановка (отсутствует очередная инструкция q_j, a_l, с которой столкнулась машина);
• зацикливание (ни одна из инструкций, выполняемых машиной, не приводит к её остановке, – машина работает бесконечно).

Машина Поста также состоит из бесконечной ленты, разделённой на клетки, и из считывающей головки. В каждую клетку ленты может быть записан либо символ «0», либо символ «1». Считывающая головка на каждом шаге считывает или записывает символ в текущую клетку и может перемещаться на одну клетку вправо или влево в соответствии с алгоритмом задачи. Входные данные для машины Поста записываются на ленте перед началом работы машины, а выходные данные получаются после того, как достигнута команда «Стоп».

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

• L – передвинуть головку на одну клетку влево;
• R – передвинуть головку на одну клетку вправо;
• 1 – записать в клетку символ «1»;
• 0 – записать в клетку символ «0»;
• ? – выполнить команду n₁, если в данной клетке записана «1», и n₂, если записан «0»;
• S – остановить машину.

Существует три различных исхода работы машины Поста:

• результативная остановка – машина нашла команду «Стоп»;
• безрезультативная остановка – машина вынуждена выполнить запрещённую операцию – записать «0» в клетку, в которой уже записан нуль, или записать «1» в клетку с единицей;
• зацикливание – машина не может найти команду «Стоп» или запрещённую операцию и работает бесконечно долго.

Машина Поста является упрощённой моделью современного компьютера, а программы для этой машины – далеким предком большинства современных языков программирования.

Нормальный алгоритм Маркова преобразовывает по определённым правилам начальную строку P в конечную строку R.

Пусть алфавит A состоит из символов  Условимся, что в A нет управляющих символов «Λ» и «.», и будем обозначать символом ξ любой из этих символов:  Пусть α и β – строки, составленные из какого-либо количества символов алфавита, то есть 

Отдельные строки этой схемы называются формулами подстановки.

Работа нормальной схемы (нормального алгоритма Маркова) состоит из отдельных шагов. На первом шаге исходное слово P = R₀заменяется на слово R₁; на втором шаге слово R₁ заменяется на слово R₂; ... на последнем шаге слово R_n – 1 заменяется на слово R_n.

На очередном, j-м, шаге преобразование происходит по следующему правилу. Просматривается нормальная схема алгоритма и из неё выбирается самая верхняя формула подстановки, левая часть которой α_i имеет вхождение в слово R_j – 1. Первое вхождение α_iв слово R_j – 1 заменяется на β_i. В результате получается слово R_j и начинается новый, (j + 1)-й шаг.

Если ни одно из слов α_i не входит в слово P, то говорят, что схема S не действует на слово P.

Нормальные алгоритмы Маркова заканчиваются результативной остановкой, если схема S не действует на заключительное словоR либо если среди формул подстановки встретилась заключительная (та, которая отмечена символом «.» сразу после стрелки). Кроме того, алгоритм может закончиться зацикливанием; в этом случае говорят, что нормальный алгоритм неприменим к этому слову.