Sekvence křížení (Turingovy stroje) - Crossing sequence (Turing machines)

v teoretická informatika, a křížení sekvence na hranici i, označeno jako ${ displaystyle { mathcal {C}} _ ​​{i} (x)}$ nebo někdy ${ displaystyle cs (x, i)}$, je posloupnost stavů ${ displaystyle q_ {i_ {1}}, q_ {i_ {2}}, ..., q_ {i_ {k}},}$ a Turingův stroj na vstupu x, takže v této posloupnosti stavů hlava prochází mezi buňkou i a i + 1 (všimněte si, že první přechod je vždy přechod vpravo a další vlevo atd.)

Někdy je křížení sekvence považováno za sekvenci konfigurace, které představují tři prvky: stavy, obsah pásek a polohy hlav.

Studium křížení sekvencí se provádí např. V teorie výpočetní složitosti.