Они были предложены в качестве формального подхода к понятию алгоритма выдающимся русским математиком А.А.Марковым в 1950-х годах.

Рассматривается некоторый алфавит A и слова в этом алфавите.

Конкатенацией двух слов Q и R назовем слово QR, то есть в конкатенации сначала идут последовательно все символы слова Q, а затем все символы слова R. (Не зная слов Q и R, мы воспринимаем слово QR как единое целое).

Любую подпоследовательность идущих друг за другом символов слова назовем подсловом.

Слово, не имеющее букв, называется пустым словом и обозначается через L.

Слова, состоящие из одинаковых последовательностей символов, считаются эквивалентными. Заметим, что слова PQ, LPQ, PLQ, PQL эквивалентны в рамках формализма НАМ.

НАМ состоит из последовательности шагов работы. При определении шагов работы НАМ используются понятия преобразования, обычного и завершающего.

Обычным преобразованием слова P назовем переход от слова P к слову S. Завершающее преобразование состоит из обычного преобразования и команды остановки, которая обозначается точкой – (·). То есть после выполнения конечного преобразования работа заканчивается.

Преобразование p_i обозначается или в виде P_i®S_i (обычное), или в виде P_i®·S_i (завершающее).

Формально НАМ - это четверка {A,B,D, P}, где A - входной алфавит ,B - надалфавит А, D - пустое слово, P - конечный упорядоченный набор преобразований P={p₁,…,p_n}. В каждом таком преобразовании присутствуют слова над алфавитом A (в алфавите B). Входное и выходное слова - это слова в алфавите A.

Если для слова P не существует ни одного преобразования такого, что P_i является его подсловом, то эту ситуацию обозначим следующим образом: PÜ. Если в результате применения НАМ к слову P образовалось слово R, то обозначим это через PÞR.

НАМ преобразует входное слово P в выходное Q. Работа НАМ осуществляется шаг за шагом. На первом шаге в качестве входного слова используется слово P. На каждом следующем шаге в качестве входного слова используется результат предыдущего шага. На каждом шаге во входном слове поочередно для i=1,…,n ищутся крайние левые подслова, эквивалентные P_i . Если такое подслово найдено, то выполняется преобразование p_i. Если это преобразование завершающее, то работа НАМ заканчивается. В противном случае переход к следующему шагу. И так для всех i=1,…,n. Если ни для какого из этих i упомянутое выше подслово не найдено, то работа НАМ заканчивается.

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

Входной алфавит - это алфавит, в котором написано входное слово. Составление НАМ - это нахождение B и P={p₁,…,p_n}. Предполагается, что пустое слово не входит ни в один из рабочих алфавитов НАМ.

Перейдем теперь к рассмотрению конкретных примеров. Договоримся о некоторых обозначениях. Целые числа задаются в алфавите {1, *}. Целое число n кодируется последовательностью из n+1 единицы. Несколько аргументов функции разделяются символом *. Например, при вычислении значения функции F(x,y,z) от трех переменных x=2, y=5, z=1 входное слово НАМ имеет вид 111*111111*11.

Для сокращения записи схемы алгоритма буквами h, x, z будем обозначать любые буквы входного алфавита A, а буквами a, b, g обозначаются конкретные буквы, не входящие в A. Например, имеем алфавит из 10 букв, а в схеме алгоритма идут подряд 10 преобразований стирания каждой одной буквы, которые могут выполняться в произвольном порядке. Все эти преобразования можно обозначать как h®D.

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

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

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

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

Одноленточная МТ

Начнем с самого простого объекта - одноленточной детерминированной МТ. Она представляет собой пятерку {S, A, F, q₀, d}, где S={q₁,…q_k} - конечное множество, элементы которого называются состояниями, A={a₁,…,a_n} - алфавит, FÍS. Элементы F называются конечными состояниями, выделено начальное состояние q₀ и схема переходов машины Тьюринга d. Каждый такой переход еще называется командой, а вся схема (список команд) представляет собой частично определенное отображение из S´A®S´A´{L, R, St}. Здесь {L, R, St } - множество из трех элементов, смысл которых ниже поясняется.

Опишем теперь механизм работы МТ. На двусторонней бесконечной ленте, разбитой на ячейке, начиная с некоторой ячейки, записано входное слово P (по одному символу в каждой ячейке). Имеется еще один объект - "головка" МТ, который характеризуется наличием определенного приписанного ей состояния и умением читать и писать.

Работа МТ состоит из последовательности тактов.

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

Вообще, положение головки, ее состояние и запись на ленте полностью описывают конфигурацию МТ в данный момент времени. Поэтому конфигурацией МТ и называется слово v₁…v_kq_jv_k+1…v_m. Эта запись свидетельствует о том, что в данный момент времени головка МТ находится в состоянии q_j и обозревает ячейку ленты, в которой записан символ v_k+1. Все же слово, записанное к этому моменту на ленте, имеет вид v₁…v_kv_k+1…v_m.

Каждой конфигурации K=v₁…v_kq_jv_k+1…v_m однозначно сопоставляется пара конфигурации q_jv_k+1и слово конфигурации v₁…v_kv_k+1…v_m.

Такт работы представляет собой переход из одной конфигурации к другой. Этот переход осуществляется путем выполнения некоторой команды q_ia_j ®q_ra_t{Z}. (Пару q_ia_j назовем левой частью команды q_ia_j®q_ra_t{Z}, а тройку q_ra_t{Z} - правой частью этой команды.) Если пара конфигурации не является левой частью ни одной из команд, то МТ останавливается и процесс ее работы заканчивается.

Если же такая команда q_ia_j ®q_ra_t{Z} найдена, то это означает, что перед выполнением данного такта МТ находилась в состоянии q_i, обозревала ячейку с символом a_j, а после выполнения данного такта она перешла в состояние q_r, в ранее обозреваемой ячейке появился символ a_t. Z имеет одно из трех значений L, R, St. В первом случае головка сдвинулась на данном такте на одну ячейку влево, во втором - вправо, в третьем - осталась на месте. Если q_r является конечным состоянием, то процесс работы МТ заканчивается и МТ останавливается. В противном случае для вновь полученной конфигурации ищется команда, правая часть которой совпадает с парой конфигурации, и процесс продолжается.

Так как каждая команда определяется однозначно, то, в отличие от НАМ, порядок команд в списке не имеет значения.

Переход от конфигурации K_i к конфигурации K_j в результате выполнения некоторого такта работы МТ обозначим через K_iú¾K_j. Если существует такая последовательность команд, что в результате их выполнения МТ перешла из конфигурации K_i к конфигурации K_j, то эту ситуацию обозначим через K_i÷ÞK_j.

Заметим, что МТ может зацикливаться. Это довольно тонкий момент в данном формализме, который восходит к тому факту в определении алгоритма, согласно которому алгоритм не обязан сам распознавать слова из своей области действия. Конечно, если мы требуем, чтобы перед началом работы была проведена проверка на соответствие входного слова области действия, то никакого зацикливания не может быть, так как уже на стадии проверки будут отсеяны те слова, на которых алгоритм не может корректно работать (слова, которым он не применим). Если же такой предварительной стадии нет, то она может быть заменена предположением о том, что у нас есть некоторый механизм идентификации зацикливаний. То есть, мы можем различать три ситуации: МТ остановилась и завершила свою работу; МТ находится в процессе работы, совершив некоторой количество переходов, и готовится к очередному такту работы; МТ зациклилась, т.е. будет работать и никогда не остановится.

Если МТ на входном слове P за конечное число тактов останавливается, то говорят, что она применима к этому слову. Последовательность конфигураций от начальной до конечной называется вычислением МТ на слове P.

В отличие от НАМ в данном формализме присутствуют такие понятия как: читающая и пишущая головка, обозреваемая ячейка, сдвиги вправо и влево и пр. Все это с точки зрения формальной схемы интуитивного понятия "алгоритм" также нуждается в формализации. Она более или менее очевидна, особенно с точки зрения людей, знакомых с азами компьютерной техники. (Заметим, что Тьюринг предложил свой формализм в 1935 году, когда о компьютерах еще и речи не было). Предположим, что все эти детали определены, и мы получили некоторый алгоритм Â_T,C. Он работает в алфавите C, C является надалфавитом алфавита A машины Тьюринга Т. А для любых слов P и Q в алфавите С соотношение Â_T,C(P)=Q выполняется тогда и только тогда, когда существует такое вычисление на машине Тьюринга Т такое, что оно начинается с конфигурации q₀P и заканчивается конфигурацией R₁q_iR₂, где R₁R₂=Q.

Вообще же произвольный алгоритм Á в алфавите D называется вычислимым по Тьюрингу тогда и только тогда, когда существует машины Тьюринга T с алфавитом A и алфавит C, являющийся надалфавитом AÈD такие, что алгоритмы Â_T,C и Á вполне эквивалентны относительно D.

Многоленточная МТ

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

Команды задаются уже отображением S´A^k®S´{A´{L, R, St}}^k.

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

Недетерминированная МТ

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

Имеется две управляющие головки (УГ) и одна лента. Одна головка Г1 - обычная, такая же, как в МТ, а вторая Г2, которая часто называется угадывающей, может только записывать. Запись на ленте представляет собой слово (условие задачи), записанное слева направо, начиная с ячейки с номером 1. В начальный момент времени обычная головка наблюдает ячейку с номером 1, а пишущая головка - ячейку с номером (-1). Вначале работает только пишущая (угадывающая) головка. На каждом такте работы она может написать символ в наблюдаемой ячейке и сдвинуться влево, либо остановиться. В последнем случае начинает работать обычная головка с состояния q₀. С этого момента НМТ работает точно так же, как МТ с той лишь разницей, что наблюдает не самый крайний слева символ входного слова.

Управляющее устройство пишущей головки принимает решение совершенно произвольно, поэтому может никогда не остановиться.

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

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

Разница между МТ и НМТ может быть проиллюстрирована с помощью сравнения модели обычных вычислений и моделью параллельных вычислений.

В качестве примеров можно рассмотреть задачи о выполнимости, о гамильтоновом цикле и о простоте числа.

Оракульная МТ

Как и в предыдущем случае здесь две головки (обычная и оракульная), но и две ленты (обычная и оракульная). Во множестве состояний выделены два особых: состояние вопроса к оракулу q_c и резюмирующее состояние q_r. Обе головки управляются одним управляющим устройством. В начальный момент времени на обычной ленте записано входное слово I, начиная с ячейки с номером 1. Все остальные ячейки обеих лент пусты.

Работа оракульной машины Тьюринга (ОМТ) почти аналогична работе двухленточной МТ. Разница в следующем. Если управляющее устройство оказывается в состоянии q_c, то поведение на следующем шаге зависит от фиксированной оракульной функции g:A*®A*.

Этот шаг не изменяет положение основной головки и запись на основной ленте. Его результатом является переход в состояние q_r и изменение за один шаг всего содержимого оракульной ленты по следующему правилу.

Пусть y - слово, записанное на оракульной ленте, начиная с первой ячейки и до ячейки, над которой находится головка. Если головка находится левее ячейки с номером один, то полагается, что y - некоторая заранее оговоренная постоянная. За данный такт на оракульной головке записывается слово g(y), начиная с первой ячейки. Остальная часть ленты стирается, а головка обозревает ее первую ячейку.

То есть мы имеем как бы комбинацию обычной машины Тьюринга М и некоторого оракула g. Вообще говоря, для одной и той же задачи могут быть использованы разные оракулы. Поэтому можно искусственно вычленить ту часть программы ОМТ, которая касается работы обычной головки. Она ведь не касается действий оракульной головки. Именно эту часть программы называют программой ОМТ. Обозначим ее через M. В случае же рассмотрения конкретного оракула g всю программу целиком будем обозначать через M_g, и называть релятивизированной программой ОМТ.