Определение машины Тьюринга

Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И также как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Именно Тьюринг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную созидательную деятельность. Такой человек, находясь в определенном «умонастроении» («состоянии»), просматривает некоторый текст. Затем он вносит в этот текст какие-то изменения, проникается новым «умонастроением» и переходит к просмотру последующих записей.

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

Опишем теперь машину Тьюринга более тщательно.

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

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

Работа машины определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда T(i,j) (i= 1, 2, ..., m; j = 0, 1, ..., n) представляет собой выражение одного из следующих видов:

q_i a_j → q_k a_l С;

q_i a_j → q_k a_l П; (1)

q_ia_j → q_k a_l Л

где 0 < k < m; 0 < l < п.

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

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

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

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

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

В следующий момент времени (если q_k ≠ q₀) машина делает шаг, регламентированный командой T(k, l): q_k a_l → q_r a_s X и т.д.

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

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

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

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

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

Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q₁ (соответственно в состоянии остановки q₀). Наконец, будем говорить, что слово α перерабатывается машиной в слово β, если от слова α, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову β, воспринимаемому в положении остановки.