Máquinas de Turing "Carlos Mario Lopera"

Máquinas de Turing "Carlos Mario Lopera"

1. Que es ?

   • Es un dispositivo teórico que manipula símbolos sobre una cinta de acuerdo con una tabla de reglas definidas
     • reglas
       • despues del primer movimiento puede ser leida y escrita hacia izquierda o derecha
       • moviendose a la derecha, Γ alfabeto de la cinta y es leida hacia izquierda o derecha
     • de una manera formal o matemáticamente son definidas como una 7 tupla
       • Σ alfabeto de transición
         • parte de vocabulario
       • Γ Alfabeto de la cinta
       • Q conjunto de estados
       • S Estado Inicial
       • F Estados Finales de aceptacion
       • b símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
       • δ tabla de estados

2. funcionamiento y configuracion de una MT

   • Una máquina de Turing transforma un INPUT en un OUTPUT después de algunos pasos. La máquina tiene un funcionamiento totalmente mecánico y secuencial.Lee el simbolo ->Toma el simbolo del estado que se encuentra -> Accede a la tabla donde lee el simbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.
     • el INPUT y OUPUT constan de números en código binario (ceros y unos)
     • puede realizar dos operaciones
       • Mover el cabezal lector/escritor hacia la derecha
       • Mover el cabezal lector/escritor hacia la izquierda
         • El cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.
     • La memoria es la cinta de la máquina que se divide en celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco".

3. Tipos de MT

   • Deterministas
     • En el caso de que para cada par (estado, símbolo) posible exista a lo sumo una posibilidad de ejecución.
   • No deterministas
     • acepta una cadena si cualquier secuencia de transiciones conduce a un estado final, tambien En el caso de que exista al menos un par (estado, símbolo) con más de una posible combinación de actuaciones

4. sus componentes son

   • cinta
   • cabezal
   • tabla
   • Registro de estado