Máquina de Turing de múltiples cintas
Las máquinas Turing de cintas múltiples tienen varias cintas en las que se accede a cada cinta con un cabezal independiente. Cada cabeza puede moverse independientemente de las otras cabezas. Inicialmente, la entrada está en la cinta 1 y otras están en blanco. Al principio, la primera cinta está ocupada por la entrada y las otras cintas se mantienen en blanco. A continuación, la máquina lee símbolos consecutivos debajo de sus cabezas y la TM imprime un símbolo en cada cinta y mueve sus cabezas.
Una máquina de Turing de múltiples cintas se puede describir formalmente como una tupla de 6 (Q, X, B, δ, q 0 , F) donde -
Q es un conjunto finito de estados
X es el alfabeto de la cinta
B es el símbolo en blanco
δ es una relación de estados y símbolos donde
δ: Q × X k → Q × (X × {Left_shift, Right_shift, No_shift}) k
Donde hay k número de cintas
q0 es el estado inicial
F es el conjunto de estados finales
Note - Cada máquina Turing de cinta múltiple tiene una máquina Turing de cinta única equivalente.