Variantes de la máquina de Turing Existen muchas alternativas de la máquina de Turing, incluyendo cintas múltiples o indeterminismo. Estas son llamadas variantes del modelo de la máquina de Turing. Tanto el modelo original como sus variantes tienen el mismo poder, es decir, reconocen la misma clase de lenguajes. Para ilustrar la robustez del modelo de la máquina de Turing, hagamos una variación de la función de transición permitida. En la definición original, la función de transición fuerza a la cabeza de la cinta a moverse a la izquierda o a la derecha después de cada paso, la cabeza de la cinta no puede permanecer sin movimiento. Supongamos que le damos a la máquina de Turing la habilidad para que la …ver más…

3. Si en algún punto S mueve una de las cabezas virtuales a la derecha sobre un símbolo #, esta acción significa que M ha movido la cabeza correspondiente sobre la porción de cinta aún no leida (con símbolos blancos). De tal forma que S escribe un símbolo blanco en su cinta y recorre una posición todos los símbolos desde ahí hasta el símbolo # más a la derecha. Después continua la simulación como antes.” ……………………………………………………………………………………………………………………………………………… Corolario Un lenguaje es reconocido por Turing si y sólo si alguna máquina de Turing multicinta lo reconoce. DEMOSTRACIÓN Un lenguaje reconocido por Turing es reconocido por una máquina de Turing ordinaria, la cual es un caso especial de una máquina de Turing multicinta. Esto prueba una dirección del corolario. La otra dirección se probó en el teorema anterior. 4.2.2. Máquina de Turing indeterminista Una máquina de Turing indeterminista se define de la forma esperada. En cada punto en una computación la máquina puede proceder de acuerdo a varias posibilidades. La función de transición para una máquina de Turing indeterminista tiene la forma δ: Q x Γ → P(Q x Γ x { L, R }) La computación de una máquina de