WikiDer > Последовательность пересечения (машины Тьюринга)
В теоретическая информатика, а последовательность пересечения границы я, обозначенный как или иногда , - последовательность состояний из Машина Тьюринга на входе x, так что в этой последовательности состояний голова пересекает ячейку я и я +1 (обратите внимание, что первое пересечение всегда правое, а следующее левое и так далее ...)
Иногда последовательность скрещивания рассматривается как последовательность конфигурации, которые представляют три элемента: состояния, содержимое лент и позиции голов.
Изучение последовательностей скрещивания проводится, например, в теория сложности вычислений.