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

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

Машина располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит А = {а₀, а₁ ..., а_п}. В каждую ячейку обозреваемой ленты в каждый дискретный мо­мент времени может быть записан только один символ из алфавита А. Ради единообразия удобно считать, что среди букв внешнего алфавита А имеется «пустая буква», и именно она записана в пустую ячейку ленты. Условимся, что «пустой буквой» или симво­лом пустой ячейки является буква а₀. Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв.

Далее, в каждый момент времени машина способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых Q = {q₀ , q₁, .., q_m}. Среди состояний выделяются два — начальное q₁ и заключительное (или состояние остановки) q₀. Находясь в состоянии q₁, машина начинает рабо­тать. Попав в состояние q₀, машина останавливается.

Находясь в какой-либо момент времени в незаключительном состоянии (т.е. в состоянии, отличном от q₀) машина совершает шаг, который полностью определяется ее текущим состоянием q_i и символом a_j, восприни­маемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой T(i,j): q_ia_j -» q_ka_l X, где X Î {С, П, Л}. Шаг заключается в том, что:

1) содержимое a_j обозреваемой на ленте ячейки стирается и на его место записывается символ а_l, (который может совпадать с a_j );

2) машина переходит в новое состояние q_k (оно также может совпадать с предыдущим состоянием q_i);

3) машина переходит к обозрению следу­ющей правой ячейки от той, которая обозревалась только что, если Х=П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С.

В следующий момент времени (если q_k¹q₀) машина делает шаг, регламентированный командой T(k, l): q_ka_l-> q_ra_sX ит.д.

Поскольку работа машины, по условию, полностью определяет­ся ее состоянием q_i в данный момент и содержимым обозревае­мой в этот момент ячейки, то для каждых q_i и a_j, (i= 1, 2, ..., т; j = 0, 1, ..., n) программа машины должна содержать одну и толь­ко одну команду, начинающуюся символами q_ia_j. Поэтому про­грамма машины Тьюринга с внешним алфавитом А = {а₀, а₁, ..., а_п} и алфавитом внутренних состояний

Q = {q₀ , q₁, .., q_m} содержит т(п + 1) команд.

Словом в алфавите А или в алфавите Q, или в алфавите AUQ называется любая последовательность букв соответствующего ал­фавита. Под k-й конфигурацией будем понимать изображение лен­ты машины с информацией, сложившейся на ней к началу k-го шага (или слово в алфавите А, записанное на ленту к началу k-го шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конеч­ные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигура­ция называется заключительной, если состояние, в котором при этом находится машина, заключительное.

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

Будем говорить, что непустое слово a в алфавите А \ {a₀} = {а₁,...,a_n} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово а. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q₁ (соответственно в состоянии остановки q₀). Наконец, будем гово­рить, что слово a перерабатывается машиной в слово b, если от слова a, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову b, воспринимаемому в положении остановки.