CLASIFICACIÓN DE MÁQUINA DE TURING

Máquina de Turing Multicinta:

En este modelo, la máquina de Turing tiene k cintas, infinitas en ambos sentidos, y k cabezales de L/E, Sólo hay una entrada de información, en la primera cinta. Los tres pasos asociados a cada transición son ahora: transición de estado, escribir un símbolo en cada una de las celdas sobre las que están los cabezales de L/E, el movimiento de cada cabezal es independiente y será R, L ó NADA (Z).

Máquina de Turing No Determinista:

Es una Máquina de Turing con cinta limitada a la izquierda, que se caracteriza por que a partir de un estado y un símbolo puede haber diferentes transiciones,
El número de transiciones asociado a cada para estado/símbolo SIEMPRE ES FINITO.

Máquina de Turing Multidimensional:

En este modelo la cinta es un array de k dimensiones de celdas, infinito en las 2k direcciones posibles. Dependiendo del estado y del símbolo leído, hay una transición que difiere de las de la Máquina de Turing unidimensional en que el movimiento puede ser en cualquiera de las 2k direcciones existentes. Se considera que la entrada está sobre un eje, y que la posición inicial del cabezal está ajustada a la izquierda de esa entrada.

Máquina de Turing con Múltiples Cabezales:

Tiene k cabezales de L/E, como la multicinta, pero con una sola cinta. Los cabezales operan todos de forma independiente. Como en las Máquinas de Turing multicinta, se admiten movimientos L, R ó Z.

 Máquina de Turing Offline:

Es un caso particular de las Máquinas de Turing multicinta: tienen una cinta especial de sólo lectura en la que el cabezal, que sólo puede moverse hacia la derecha, no puede moverse de la zona delimitada por una par de símbolos especiales.