2020-01-14
347
Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы.
Машины Тьюринга – это совокупность следующих объектов
1) внешний алфавит A={ a 0, a 1, …, a n};
2) внутренний алфавит Q={ q 1, q 2,…, q m} – множество состояний;
3) множество управляющих символов {П, Л, С}
4) бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;
5) управляющее устройство, способное находиться в одном из множества состояний
Символом пустой ячейки является буква внешнего алфавита а 0.
Среди состояний выделяются два – начальное q 1, находясь в котором машина начинает работать, и заключительное (или состояние остановки) q 0, попав в которое машина останавливается.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы алфавита A. Управляющее устройство работает согласно командам, которые имеют следующий вид
q i a j → a pX q k
Запись означает следующее: если управляющее устройство находится в состоянии q i, а в обозреваемой ячейке записана буква a j, то (1) в ячейку вместо a j записывается a p, (2) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходит в состояние q k.
Поскольку работа машины, по условию, полностью определяется ее состоянием q, в данный момент и содержимым а обозреваемой в этот момент ячейки, то для каждой возможной конфигурации q i a j имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Поэтому программа машины Тьюринга с внешним алфавитом A={ a 0, a 1, …, a n} и внутренним Q={ q 1, q 2,…, q m} содержит не более m (n+ 1) команд.
Словом в алфавите А или в алфавите Q, или в алфавите A 
Q называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-того шага (или слово в алфавите А, записанное на ленту к началу k-того шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.
Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.
Будем говорить, что непустое слово б в алфавите А\ { а 0} = { a 1, …, a n} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справа ячейку из тех, в которых записано слово б. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (соответственно в состоянии остановки q 0).
Если обработка слова б переводит машину Тьюринга в заключительное состояние, то говорят, что она применима к б, в противном случае – не применима к б (машина работает бесконечно)
Рассмотрим пример:
Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 – символ пустой ячейки), алфавитом внутренних состояний Q = { q 0, q 1, q 2} и со следующей функциональной схемой (программой):
q 1 0 → 1 Л q 2;
q 1 1 → 0 С q 2;
q 2 0 → 0 П q 0;
q 2 1 → 1 С q 1;
Данную программу можно записать с помощью таблицы
| 0 | 1 | |
| q 1 | 1 Л q 2 | 0 С q 2 |
| q 2 | 0 П q 0 | 1 С q 1 |
Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:
q 1
| … | 1 | 1 | 0 | … |
На первом шаге действует команда: q 1 0 → 1 Л q 2 (управляющее устройство находится в состоянии q 1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q 2), в результате на машине создается следующая конфигурация:
q 2
| … | 1 | 1 | 1 | … |
На втором шаге действует команда: q 2 1 → 1С q 1 и на машине создается конфигурация:
q 1
| … | 1 | 1 | 1 | … |
Третий шаг обусловлен командой: q 1 1 → 0 С q 2. В результате нее создается конфигурация:
q 2
| … | 1 | 0 | 1 | … |
Наконец, после выполнения команды q 2 0 → 0 П q 0 создается конфигурация
q 0
| … | 1 | 0 | 1 | … |
Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q 0.
Таким образом, исходное слово 110 переработано машиной в слово 101.
Полученную последовательность конфигураций можно записать более коротким способом (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина):
11 q 10 => 1 q 211 => 1 q 111 => 1 q 201 => 10 q 01
Машина Тьюринга – не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A 
Q, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.
