Техніка слідів. Лема про заміщення

Рассмотрим вычислит. процесс, обозначаемый M[P], который выполняет МТ М, запущенная в начальной конфигурации с исходным словом р. Пронумеруем границы между соседними ячейками так:

С каждой фиксированной границей j можно ассоциировать послед-сть внутренних состояний МТ след. образом: если в процессе М[P] головка ни разу не пересекает границу j, то эта последовательность пуста (не содержит никаких элементов). Пусть головка пересекает границу j ровно s раз: первый раз в состоянии q(1), 2-ой – в состоянии q(2) и т.д. Тогда последовательность q(1), q(2),…, q(s), являющаяся словом в алфавите Q внутренних состояний, называется следом процесса M[P] в точке j и обозначается след_M(P, j). Это обозначение содержит указание на рассматриваемую машину М и на исходное слово Р. Однако в тех случаях, когда из контекста ясно, какая имеется в виду машина или слово, будем применять упрощенніе обозначения типа след(Р, j) или след(j). Если первое прохождение головки было слева направо, то второе будет справа налево и далее направление будет также чередоваться. Ясно, что при j>0 первое прохождение будет только слева направо, а при j£0 – в противоположном направлении. Если процесс M[P] бесконечен, то может случиться, что в некоторых границах j след также будет бесконечен. Однако поскольку мы далее будем рассматривать только конечные процессы, заканчивающиеся выдачей результирующего слова R (зависящего от исходного слова P), то и следы будут конечными. Пусть |след(j)| обозначает длину следа в т. j, т. е. число пересечений границы j. Очевидно, что каждое пересечение головкой какой-либо границы связано с затратой 1 такта работы МТ. Поэтому справедливо нер-во: t_M(P)³S|след(P, j)| (1), где суммирование берется по любому мн-ву границ. Строгое нер-во может возникнуть за счет того, что рассматривается лишь часть границ, пересекаемых головкой, а также по той причине, что на некоторых тактах головка не сдвигается с обозреваемой ячейки, а следовательно не совершается никаких пересечений. Иногда анализ процесса M[P] позволяет обнаружить, что в некоторых точках возникают достаточно длинные следы. В таких случаях нер-во (1) может послужить для установления нижней оценки сигнализирующей t_M(P).