Последовательность пересечений (машины Тьюринга)

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

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

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