Машина Тьюринга — математическое понятие алгоритма.

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

Что есть в каждой машине Тьюринга? Есть три конечных множества A, Q и Т и программа, полностью определяющую работу машины Тьюринга.

Что же представляет собой программа?

Каждой паре вида (s_i, q_i), где s_iÎА и q_iÎQ\{q₀}, соответствует тройка (s_j, t, q_j), где s_jÎA, tÎT и q_jÎQ (q₀ не участвует в парах (s_i, q_i), так как паре (s_i, q₀) уже ничего не соответствует, машина останавливается в заключительном состоянии q₀).

 

Множество всех пар вида (s_i, q_i), где s_iÎA и q_iÎQ\{q₀}, называется произведением множеств А и Q\{q₀} и обозначается А´Q\{q₀}. Аналогично, множество всех троек вида (s_j, t, q_j), где s_jÎA, tÎT и q_jÎQ, называется произведением множеств А, Т и Q и обозначается А´Т´Q.

 

Таким образом, программа машины Тьюринга представляет собой функцию с областью определения А´Q\{q₀}, принимающую значения из множества А´Т´Q, или отображение первого множества во второе: А´Q\{q₀}®A´T´Q

 

Машиной Тьюринга (МТ) называется система вида (A, s₀, Q, q₁, q₀, T, t),

где А - конечное множество - алфавит МТ,

s₀ÎA и называется пустой буквой алфавита,

Q - конечное множество, элементы которого называются состояниями МТ (Q - множество состояний МТ),

q₁ÎQ, q₁ - начальное состояние МТ,

q₀ÎQ, q₀ - пассивное или заключительное состояние МТ,

Т={Л, Н, П} - множество сдвигов МТ,

t:А´Q\{q₀}®A´T´Q, t - программа МТ.

 

Нетрудно убедиться в том, что в этом определении фигурируют только математические и логические термины (или символы): множество, конечное множество, элемент множества, отношение принадлежности (Î), функция (®), произведение множеств, есть (—), равно (=). И никакие другие, нематематические или нелогические понятия в приведенной формулировке не используются.

 

Машина Тьюринга перерабатывает слова в алфавите машины согласно программе этой машины.

 

Какую бы МТ, имеющую алфавит A={s₀, s₁,..., s_k}, состояния q₀, q₁,..., q_p и программу t, мы ни взяли, можем считать, что имеется алгоритм, исходными объектами, промежуточными и окончательными результатами которого являются слова в алфавите А. Предписанием, задающим этот алгоритм, является программа t.

 

Другими словами, с математической точки зрения МТ — это алгоритм для переработки слов в алфавите этой машины (ради удобства отождествляем МТ с ее программой).

 

Проиллюстрируем основные свойства алгоритмов на примере МТ.