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

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

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

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

Представим совокупность всех возможных исходных данных, перерабатываемых каким-либо алгоритмом А в виде последовательности

₁ , ₂ , … , _i , … ,

а все возможные результаты - в виде последовательности

₁ , ₂ , … , _j , … .

Тогда любой алгоритм А_k , преобразующий исходные данные _i в результат _j, можно свести к вычислению функции _k , указывающей номер результата j по номеру совокупности исходных данных i

j = _k (i).

Но индексы i и j являются целыми числами и всегда могут быть записаны в двоичной системе счисления при помощи конечного набора нулей и единиц. При этом функция _k может рассматриваться как логическая функция, преобразующая ситуацию i на входе автомата в ситуацию j на его выходе.

Следовательно, любой алгоритм в принципе может быть реализован при помощи соответствующего дискретного автомата.

Английский математик Тьюринг предложил абстрактную схему автомата, принципиально пригодного для реализации любого алгоритма. Этот автомат, получивший название "Машина Тьюринга" является автоматом с бесконечной памятью.

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

В каждой из ячеек может быть записан нуль или единица. Над лентой перемещается головка Т, управляемая автоматом L, обладающим конечной памятью. Автомат L работает тактами. На его вход поступает информация о символе (0 или 1), считываемой головкой с ленты. Под влиянием команд, получаемых каждый такт от автомата L, головка может оставаться на месте или передвигаться на одну ячейку вправо или влево. Одновременно головка получает от автомата L команды, под влиянием которых она может заменить символ, записанный в ячейке, над которой она находится.

Действие машины Тьюринга однозначно определяется исходным заполнением ячеек ленты и оператором преобразования управляющего автомата, который может быть задан таблицей переходов. Обозначим через S_i (S₀=0, S₁=l) символ, считываемый головкой, через R_J (R₀ – стоп, R₁ - влево, R₂ - вправо) - команду на перемещение головки и через q_k (k=1,2, … , n) - состояние управляющего автомата. Тогда его таблица переходов может быть представлена таким образом (табл. 3.2).

Как видно из табл. 3.2, действие автомата зависит от входа S и его состояния q. Определенным значениям S_i и q_i соответствует определенная совокупность значений трех величин: S, R и q, обозначающих соответственно: какой символ S запишет головка на ленту, какова будет команда R на перемещение головки и в какое новое состояние q перейдет автомат L. Следует иметь в виду, что среди состояний q автомата L должно быть по крайней мере одно такое его состояние q^*, при котором: головка не изменяет символа S, команда R=R₀ (стоп) и автомат остается в состоянии покоя q^*. Придя в состояние q^*, автомат заканчивает выполнение алгоритма, и дальнейшая работа машины Тьюринга прекращается.

Таблица 3.2 – Таблица переходов

Состояние	Вход
	S0=0	S1=1
q1 q2 q3 …	S0 , R2 , qk S1 , R0 , qs S1 , R1 , qp …	S1 , R1 , qm S0 , R1 , ql S0 , R2 , qs …

Пусть, например, таблица перехода автомата L имеет следующий вид (табл. 3.3)

Таблица 3.3 – Таблица переходов

Q	S
	0	1
q* q1	0, R0 , q* 1, R0 , q*	1, R0 , q* 1, R2 , q1

Тогда, если в начальный момент автомат находится в состоянии q₁, а головка расположена над ячейкой, в которой записан символ 1, то головка будет перемещаться вправо до тех пор, пока не обнаружит ячейку с символом 0, заменит его символом 1 и остановится. Если начальное состояние системы (состояние в нулевой такт) и заполнение ленты соответствуют требуемым, то, согласно табл. 3.3 система в последующие два такта перейдет в состояния, показанные в табл. 3.3, и на втором такте остановится.

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

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