Язык конфигураций

Пусть в момент времени t самая левая непустая ячейка ленты содержит символ , а самая правая непустая ячейка содержит символ В этом случае будем говорить, что в момент t на ленте записано слово При S = 1, т.е. когда на ленте только один непустой символ Р = . Если в момент времени t автомат находится в состоянии и в обозреваемой ячейке записан символ слова то слово называется конфигурацией машины Тьюринга в момент t. Конфигурация, соответствующая началу работы машины, называется начальной. Результирующая конфигурация называется заключительной. Если в некоторый момент времени конфигурация машины была K, а в следующий момент , то конфигурация называется непосредственно выводимой из K и обозначается это так: K╞ . Если ╞ при , то последовательность конфигураций называется вычислением по Тьюрингу. В этом случае пишем ├ и говорим выводима из ”. Здесь – начальная конфигурация. Если – заключительная конфигурация, то применяют запись ├. (читается: заключительно выводима из ). Если машина , начав работу на слове , остановится через определенное число шагов, то говорят, что машина Т применима к слову Р, а результат применения обозначается Т(Р). Если машина не остановится, то говорят, что машина Т не применима к слову Р. Машины и называются эквивалентными, если для любого Р слова и определены или не определены одновременно, и если они определены, то = .