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.