Multicinta

  Maquina de Turing Multicinta

La máquina de Turing multicinta tiene varias cintas, cada una de las cuales tiene su propia cabeza de lectura/escritura. Las cabezas de lectura/escritura se controlan independientemente (es decir, al mismo tiempo, no tienen que moverse en la misma dirección, ni realizar el mismo número de movimientos, ni incluso, hacer nada a la vez). En un solo movimiento, esta máquina de Turing:

1. Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que están analizando actualmente las cabezas de lectura/escritura.

2. Escriben un nuevo símbolo en cada una de las celdas barridas por sus cabezas de lectura/escritura.

3. Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha (de forma independiente al resto de las cabezas).

Por tanto, la función de transición para una máquina de Turing con n cintas, es de la forma d : Q x G n ® Q x G n x {R, L} n donde una transición de la forma d (q, (s 1, s 2,…, s n)) = (p,(t 1, t 2, …, t n), (X1, X2, …, Xn)) significa que cambia del estado q a p, reemplaza s i por t i en la cinta i y mueve la cabeza de la cinta i en la dirección Xi.