Работа машины полностью определяется заданием в первый (начальный) момент: 1) слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); 2) положения головки; 3) внутреннего состояния машины. Совокупность этих трех условий (в данный момент) называется конфигурацией (в данный момент). Обычно в начальный момент внутренним состоянием машины является q1, а головка находится либо над первой слева, либо над первой справа клеткой ленты.
Заданное слово на ленте с начальным состоянием q1 и положение головки над первым словом называется начальной конфигурацией [8]. В противном случае говорят, что машина Тьюринга не применима к слову начальной конфигурации.
Другими словами, в начальный момент конфигурация представима в следующем виде: на ленте, состоящей из некоторого числа клеток, в каждой клетке записан один из символов внешнего алфавита A, головка находится над первой слева или первой справа клеткой ленты и внутренним состоянием машины является q1. Получившееся в результате реализации этой команды слово на ленте и положение головки называется заключительной конфигурацией. 1,2,8].
Например, если в начальный момент на ленте записано слово, то начальная конфигурация будет иметь вид:
Под клеткой, над которой находится головка, указывается внутреннее состояние машины.
Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применится команда с левой частью q1a1.
Итак, зная программу и задав начальную конфигурацию, полностью определяем работу машины над словом в начальной конфигурации.
Если в работе машины Тьюринга в некоторый момент t выполняется команда, правая часть которой содержит q0, то в такой момент работа машины считается законченной, и говорят, что машина применима к слову на ленте в начальной конфигурации. В самом деле, q0 не встречается в левой части ни одной команды — этим и объясняется название q0 «заключительное состояние». Результатом работы машины в таком случае считается слово, которое будет записано на ленте в заключительной конфигурации, т. е. в конфигурации, в которой внутреннее состояние машины есть q0. Если же в работе машины ни в один из моментов не реализуется команда с заключительным состоянием, то процесс вычисления будет бесконечным. В этом случае говорят, что машина не применима к слову на ленте в начальной конфигурации.
