Comprender las máquinas de Turing: lenguajes reconocibles y decidibles

He buscado toneladas de recursos y, aunque conceptualmente entiendo la máquina de Turing en sí misma y lo que hace, estoy un poco atascado en los lenguajes Turing Recognizable y Turing Decidible y no estoy seguro de si la idea que tengo sobre ellos es correcta o equivocado.

Mi profesor define cuatro acciones posibles que una máquina de Turing puede realizar en una cadena de entrada dada:

  • Cuelgue: la máquina de Turing se sale del extremo izquierdo de la cinta y se "cuelga"
  • Bucle: la máquina de Turing hace un bucle, nunca se detiene
  • Acepta: la máquina de Turing se detiene en un estado de aceptación
  • Rechazos: la máquina de Turing se detiene en un estado de rechazo

¿Es un lenguaje reconocible de Turing solo uno que puede colgarse o hacer un bucle? ¿Cómo determino si se puede colgar o hacer un bucle? Simplemente ejecútelo a través de la máquina y si no se detiene en el estado de rechazo (o aceptación) y no es parte del lenguaje de la MT, entonces determino que no es decidible, ¿entonces debe ser reconocible? Y luego, lo que decide es si se garantiza que el lenguaje aceptará o rechazará. ¿Qué pasa con los idiomas que no son reconocibles? ¿Qué harían? Porque parece que todos los idiomas serían reconocibles a menos que fuera posible que el idioma no estuviera en el idioma de la máquina de turing, pero de todos modos se detiene en el estado de aceptación. Lo que parece que se debe a un mal diseño de la máquina de Turing en lugar del lenguaje en sí.

Estoy luchando por entender estas dos definiciones. He estado estudiando durante horas para mi examen que es mañana y simplemente no puedo entender lo que debería ser un concepto simple. Por favor, ¿ayuda a aclarar mi confusión?

No sé sobre cuelgues, ese es un concepto innecesario. Turing decidible significa que se detiene en un estado de aceptación si la palabra ingresada está en el idioma y se detiene en un estado de rechazo si la palabra no está en el idioma. Turing reconocible significa que se detiene en un estado de aceptación si la palabra está en el idioma. y en un estado de rechazo o no se detiene si la palabra no está en el idioma. Hay idiomas que no son reconocibles. El argumento más simple es un argumento de cardinalidad. Hay innumerables idiomas, y solo contablemente muchas máquinas de Turing.

Respuestas (1)

Un idioma L se dice que es recursivamente enumerable si existe una máquina de Turing METRO que cumplan las siguientes condiciones:
-Por cada ω ∈ L , simulando METRO en ω (que denotamos METRO ( ω ) ) resulta en METRO detener y aceptar ω . -Para cada ω ∈ Σ ∗ ∖ L , METRO no acepta ω .

Tenga en cuenta que para un lenguaje recursivamente enumerable, cualquier TM que acepte L no es necesario detenerse en las entradas fuera del idioma.

Si L es decidible, debe existir algún TM que se detenga en todas las entradas además de las condiciones para L siendo recursivamente enumerable.

¿Qué pasa con los idiomas que no son reconocibles?

No existiría tal decisor o reconocedor. Considere el siguiente lenguaje: L norte O T − H A L T = { ⟨ METRO i ⟩ , ω i : METRO i es el i ª TM y ω i es el i la cuerda en Σ ∗ y METRO i no se detiene ω i } .

El idioma L norte O T − H A L T no es recursivamente enumerable. Ninguna TM puede aceptar todas las cadenas en METRO i . Para algunas TM en L norte O T − H A L T , puede ser posible reconocer un bucle infinito comprobando los estados y la función de transición. Sin embargo, no existe un procedimiento general para hacer esto para todas las MT en L norte O T − H A L T . Un argumento diagonal de Cantor prueba esto. Ver la indecidibilidad del problema de la detención.

¿Esto aclara las cosas?

Comprender las máquinas de Turing: lenguajes reconocibles y decidibles
RespuestasAquíPolítica de privacidad1y, 0v