Una máquina de Turing multipista es un tipo específico de multi-cinta de la máquina de Turing .
En una máquina Turing estándar de n cintas, n cabezales se mueven independientemente a lo largo de n pistas. En una máquina de Turing de n pistas, un cabezal lee y escribe en todas las pistas simultáneamente. Una posición de cinta en una máquina de Turing de n pistas contiene n símbolos del alfabeto de la cinta. Es equivalente a la máquina estándar de Turing y, por lo tanto, acepta con precisión los lenguajes enumerables de forma recursiva .
Definicion formal
Una máquina de Turing multipista con -las cintas se pueden definir formalmente como una tupla de 6 , dónde
- es un conjunto finito de estados
- es un conjunto finito de símbolos llamado alfabeto de cinta
- es el estado inicial
- es el conjunto de estados finales o de aceptación .
- es una función parcial llamada función de transición .
- A veces también se denota como , dónde .
Se puede definir una variante no determinista reemplazando la función de transición por una relación de transición .
Prueba de equivalencia a la máquina de Turing estándar
Esto demostrará que una máquina Turing de dos pistas es equivalente a una máquina Turing estándar. Esto se puede generalizar a una máquina de Turing de n pistas. Sea L un lenguaje recursivamente enumerable. Sea M =Ser una máquina Turing estándar que acepta L. Let M 'es una máquina Turing de dos pistas. Para probar M = M 'debe demostrarse que M M y M' METRO
Si se ignoran todas las pistas excepto la primera, entonces M y M 'son claramente equivalentes.
El alfabeto de cinta de una máquina de Turing de una pista equivalente a una máquina de Turing de dos pistas consiste en un par ordenado . El símbolo de entrada a de una máquina de Turing M 'puede identificarse como un par ordenado [x, y] de la máquina de Turing M. La máquina de Turing de una vía es:
M = con la función de transición
Esta máquina también acepta L.
Referencias
- Thomas A. Sudkamp (2006). Idiomas y máquinas, tercera edición. Addison-Wesley. ISBN 0-321-32221-5 . Capítulo 8.6: Máquinas de cintas múltiples: págs. 269–271