1. se detiene en todas las entradas: El TM eventualmente debe llegar a un estado de aceptación o un estado de rechazo, independientemente de la cadena de entrada. No puede recorrer para siempre.
2. acepta cadenas en el idioma l: Si una cadena 'W` está en L, el TM se detiene en un estado de aceptación.
3. rechaza las cuerdas que no están en el idioma l: Si una cadena `W` no está en L, el TM se detiene en un estado de rechazo.
En otras palabras, un lenguaje decidible tiene una máquina Turing que actúa como un probador de membresía perfecto:siempre da una respuesta "sí" o "no" y siempre lo hace en un tiempo finito.
Aquí hay un desglose de las técnicas y consideraciones comunes:
1. Construyendo una descripción de una máquina Turing (TM):
* Descripción de alto nivel: Comience con una descripción clara y legible por humanos del algoritmo de TM. Esto debería explicar la lógica y los pasos que se necesitan para procesar la entrada. Piense en ello como pseudocódigo.
* Descripción de nivel de implementación (opcional): * Puede * proporcionar una descripción de nivel inferior, especificar los estados, la función de transición, el alfabeto de cinta, etc. Esto a menudo es tedioso y no se requiere a menos que se solicite explícitamente, o si el algoritmo es muy sutil y requiere una definición precisa. Concéntrese primero en la descripción de alto nivel.
* La claridad es clave: Lo más importante es que su descripción es comprensible y convincente. Una descripción de alto nivel mal escrita puede ser más difícil de entender que una descripción formal bien escrita.
2. Estrategias generales para diseñar decisores:
* Simular otras máquinas: Si puede demostrar que L se puede decidir simulando otro idioma decidible (o múltiples idiomas), ha demostrado que L es decidible. La decidabilidad está cerrada bajo muchas operaciones (sindicato, intersección, complemento, concatenación, Kleene Star).
* Convierta a un problema más simple: Intente reformular el problema en un problema equivalente pero más fácil de resolver.
* Considere los casos base y la recursión: Si el problema tiene una estructura recursiva, un algoritmo recursivo se puede traducir a una decisiva de la máquina Turing. Asegúrese de que la recursión esté limitada para garantizar la terminación.
* Búsqueda exhaustiva: Si el espacio de entrada es finito o puede estar limitado, a menudo puede usar una búsqueda exhaustiva para verificar todas las posibilidades. El punto crucial es que la búsqueda debe estar garantizada para terminar.
* Aproveche los idiomas decidibles conocidos: Construya sobre el conocimiento de que ciertos idiomas ya son decidibles. Por ejemplo, idiomas regulares, idiomas sin contexto y muchos otros.
3. Técnicas para demostrar la terminación:
* Contando: Demuestre que el algoritmo involucra un contador que aumenta o disminuye estrictamente hacia un límite.
* Tamaño decreciente: Demuestre que cada paso del algoritmo reduce el tamaño del problema hasta que alcanza un caso base trivial.
* Sin bucles infinitos: Argumenta de manera convincente que el algoritmo no puede ingresar a un bucle infinito. Esto podría implicar mostrar que la máquina siempre mueve la cabeza de la cinta, o que los estados visitados siempre son distintos en un cierto período.
* Longitud de simulación: Si el algoritmo simula otro TM, establezca un límite superior en el número de pasos que tomará la simulación. Esto a menudo depende del tamaño de entrada.
4. Ejemplos y escenarios comunes:
* Idiomas regulares: Para mostrar un idioma regular es decidible, proporcione un DFA para el idioma. Un TM puede simular el DFA y detenerse en un estado de aceptación o rechazo basado en el estado final del DFA.
* Lenguajes sin contexto: Use el algoritmo CYK o un algoritmo de análisis similar. Estos algoritmos tienen un tiempo de ejecución finito.
* indecidabilidad: Comprender el problema de detención. * No puede * decidir si una máquina de Turing arbitraria se detiene en una entrada arbitraria. Si puede reducir el problema de detención a su problema, ha demostrado que su problema es indecidible (no es decidible).
* Prueba de vacío: Mostrar un idioma es * vacío * (no contiene cadenas) a veces es más fácil que mostrar que es decidible. Por ejemplo, el lenguaje de una máquina Turing es * no * decidible. Sin embargo, dado un DFA o CFG, determinar si el lenguaje que representa está vacío * es * decidible.
5. Qué no hacer:
* No solo afirme que es decidible sin justificación. Debe proporcionar un argumento razonable, que generalmente significa describir el algoritmo.
* No proporcione un TM que * solo * acepte cadenas en el idioma. También debe * rechazar * cadenas * no * en el idioma y debe detenerse.
* No proporcione un algoritmo que * pueda * detenerse pero tiene el potencial de recorrer para siempre. Un decisor * debe * detenerse.
* No confunda la decidibilidad con el reconocimiento. Un lenguaje reconocible solo requiere que una TM se detenga y acepte si la entrada está en el idioma. Puede recorrer para siempre si la entrada no está en el idioma. Los idiomas decidibles siempre son reconocibles, pero lo contrario no es cierto.
* No intentes proporcionar una "prueba con el ejemplo". Mostrar que se acepta o rechazado una entrada específica no prueba nada sobre la decidibilidad del idioma.
Ejemplo 1:a ={0
* Descripción de alto nivel:
1. Escanee la cadena de entrada para asegurarse de que consiste solo en 0s seguido de 1s. Si no, rechazar.
2. Mientras quedan 0s y 1s:
* Cruza la izquierda más 0.
* Cruza la izquierda más 1.
3. Si no quedan 0s y no 1, acepta.
4. Si solo quedan 0s o solo 1, rechace.
* Justificación: Este algoritmo se detiene para todas las entradas. Los pasos 1 y 3/4 están terminando los cheques. El paso 2 cruza uno 0 y uno 1 en cada iteración. El número de 0 y 1 es finito, por lo que el bucle terminará. Si el número de 0 y 1 era igual, aceptamos. De lo contrario, rechazamos.
Ejemplo 2:Dado un DFA D, ¿está su lenguaje l (d) vacío? A DFA ={
* Descripción de alto nivel:
1. Marque el estado de inicio de D.
2. Repita hasta que no se marquen los estados nuevos:
* Marque cualquier estado que se pueda alcanzar desde un estado actualmente marcado siguiendo una flecha en D.
3. Si algún estado de aceptación de D está marcado, rechace.
4. De lo contrario, aceptar.
* Justificación: Este algoritmo se detiene. El paso 2 explora todos los posibles estados accesibles. El número de estados en D es finito, por lo que el bucle terminará. Si podemos llegar a un estado de aceptación, el idioma no está vacío y rechazamos. De lo contrario, lo es y aceptamos. Tenga en cuenta que se garantiza que `D` es un DFA por suposición y, por lo tanto, tiene estados finitos.
Al seguir estas estrategias y comprender las propiedades de las máquinas Turing y los idiomas decidibles, puede demostrar efectivamente que un idioma es decidible. Recuerde centrarse en una descripción del algoritmo clara y convincente y un argumento sólido para su terminación y corrección.