Variación de la máquina de Turing

Prerrequisito – Máquina de Turing 

1. Máquina de Turing de múltiples vías: 
 

• Una máquina de Turing con k-pistas (para algunos k>0) tiene k-pistas y un cabezal R/W que las lee y escribe todas una por una.
• Una máquina de Turing de k-pista puede ser simulada por una máquina de Turing de una sola pista

2. Máquina de Turing de cinta infinita bidireccional: 
 

• La cinta infinita de la máquina de Turing de cinta infinita bidireccional no tiene límites en ambas direcciones, izquierda y derecha.
• La máquina de Turing de cinta infinita bidireccional se puede simular mediante una máquina de Turing infinita unidireccional (máquina de Turing estándar).

3. Máquina de Turing multicinta: 
 

• Tiene varias cintas y está controlado por un solo cabezal.
• La máquina Turing Multi-tape es diferente de la máquina Turing k-track, pero el poder expresivo es el mismo.
• La máquina de Turing de varias cintas se puede simular con una máquina de Turing de una sola cinta.

4. Máquina de Turing de múltiples cabezales y cintas múltiples: 
 

• La máquina de Turing multicinta tiene múltiples cintas y múltiples cabezales
• Cada cinta está controlada por un cabezal separado.
• La máquina de Turing de múltiples cabezales y cintas múltiples se puede simular con una máquina de Turing estándar.

5. Máquina de Turing de cinta multidimensional: 
 

• Tiene cinta multidimensional donde la cabeza puede moverse en cualquier dirección que sea izquierda, derecha, arriba o abajo.
• La máquina de Turing de cinta multidimensional se puede simular mediante una máquina de Turing unidimensional

6. Máquina de Turing de cabezales múltiples: 
 

• Una máquina de Turing de cabezales múltiples contiene dos o más cabezales para leer los símbolos en la misma cinta.
• En un solo paso, todas las cabezas detectan los símbolos escaneados y se mueven o escriben de forma independiente.
• La máquina de Turing de varios cabezales se puede simular con una máquina de Turing de un solo cabezal.

7. Máquina de Turing no determinista: 
 

• Una máquina de Turing no determinista tiene una única cinta infinita unidireccional.
• Para un estado dado y el símbolo de entrada tiene al menos una opción para moverse (número finito de opciones para el próximo movimiento), cada opción tiene varias opciones de la ruta que podría seguir para una string de entrada dada.
• Una máquina de Turing no determinista es equivalente a la máquina de Turing determinista.