любую клетку, т.к. все они пусты. После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой строки (т.к. автомат находится в состоянии q1) и того столбца, который соответствует первому символу входного слова (это необязательно левый столбец таблицы), и выполняется такт, указанный в этой ячейке.
В результате автомат окажется в новой конфигурации. Теперь такие же действия повторяются, но уже для новой конфигурации: в таблице отыскивается ячейка, соответствующая состоянию и символу этой конфигурации, и выполняется такт из этой ячейки. И так далее. Когда завершается выполнение программы? Введём понятие такта останова. Это такт, который ничего не меняет: автомат записывает в видимую клетку тот же символ, что и был в ней раньше, не сдвигается и остается в прежнем состоянии, т.е. это такт S,N,q для конфигурации (S, q). Попав на такт останова, МТ, по определению, останавливается, завершая свою работу.
Правила выполнения программы: К началу выполнения программы машина Тьюринга находится в начальной конфигурации. Эта начальная конфигурация определена следующим образом. Во-первых, на ленте записано входное слово, к которому будет применена программа. Входное слово – это конечная последовательность символов, записанных в соседних клетках ленты. Во-вторых, автомат установлен в состояние q1 (указанное в таблице первым) и размещен под его первым (самым левым) символом входного слова: