Последовательность пересечения (машины Тьюринга) - Crossing sequence (Turing machines)

В теоретическая информатика, а последовательность пересечения границы я, обозначенный как ${\displaystyle {\mathcal {C}}_{i}(x)}$ или иногда ${\displaystyle cs(x,i)}$, - последовательность состояний ${\displaystyle q_{i_{1}},q_{i_{2}},...,q_{i_{k}},}$ из Машина Тьюринга на входе x, так что в этой последовательности состояний голова пересекает ячейку я и я +1 (обратите внимание, что первое пересечение всегда правое, а следующее левое и так далее ...)

Иногда последовательность скрещивания рассматривается как последовательность конфигурации, которые представляют три элемента: состояния, содержимое лент и позиции голов.

Изучение последовательностей скрещивания проводится, например, в теория сложности вычислений.