Decidibilidad, semidecidibilidad e indecidibilidad en TOC

Conocemos los problemas decidibles, semidecidibles e indecidibles y, en este artículo, definiremos brevemente estos problemas y proporcionaremos las preguntas más frecuentes sobre estos problemas y los clasificaremos en consecuencia. 

Requisito previo: https://www.geeksforgeeks.org/decidable-and-undecidable-problems-in-theory-of-computation/

Introducción:
Identificar el tipo de idioma es una pregunta muy frecuente en Gate y otros exámenes. Sin embargo, hay algunos problemas que se plantean con frecuencia y aquí, en este artículo, discutiremos todos esos problemas. También resolveremos algunos ejemplos en este artículo para aclarar el tema. 

Problemas decidibles:  
Los problemas decidibles son aquellos problemas para los que existe una máquina de Turing correspondiente que se detiene en cada entrada con una respuesta: sí (aceptar) o no (rechazar). También se llama Turing Decidible.

Problemas semidecidibles: 
los problemas semidecidibles son aquellos problemas en los que una máquina de Turing se detiene en la entrada aceptada por ella, pero puede repetirse para siempre o detenerse en la entrada rechazada por la máquina de Turing. También se le llama problemas reconocibles de Turing.

Problemas indecidibles: 
los problemas indecidibles son aquellos problemas para los que no existe una máquina de Turing que siempre se detenga una cantidad infinita de tiempo para dar una respuesta como ‘sí’ o ‘no’. Un problema indecidible no tiene un algoritmo para determinar la respuesta para una entrada dada. Puede ser parcialmente decidible pero nunca decidible. También se les conoce como Lenguaje Enumerable No Recursivamente. 

Tabla de clasificación:
ahora clasificaremos los problemas más frecuentes como decidibles, semidecidibles e indecidibles. Aquí, en las tablas a continuación, D significa Decidible, SD significa Semi-Decidible y NR significa No-Recursivamente Enumerable. Undecidible puede ser un lenguaje Semi-Decidible o No-Recursivamente Enumerable.

	Lenguaje habitual	Lenguaje libre de contexto determinista	Lenguaje libre de contexto	Lenguaje sensible al contexto/lenguaje recursivo	Lenguaje recursivamente enumerable
Problema de detención	D	D	D	D	Dakota del Sur
Problema de membresía	D	D	D	D	Dakota del Sur
Problema de vacío	D	D	D	NR	NR
Problema de finitud	D	D	D	NR	NR
Problema de totalidad	D	D	NR	NR	NR
Problema de equivalencia	D	D	NR	NR	NR
Problema disjunto	D	NR	NR	NR	NR
Problema de contención de conjuntos	D	NR	NR	NR	NR

Tabla de clasificación de decidibilidad:
otra tabla es la siguiente.

	Lenguaje habitual	Lenguaje libre de contexto determinista	Lenguaje libre de contexto	Lenguaje sensible al contexto/lenguaje recursivo	Lenguaje recursivamente enumerable
No detener el problema	D	D	D	D	NR
No es un problema de membresía	D	D	D	D	NR
Problema de no vacío	D	D	D	Dakota del Sur	Dakota del Sur
Problema de no finitud	D	D	D	NR	NR
Problema de no totalidad	D	D	Dakota del Sur	Dakota del Sur	NR
Problema de no equivalencia	D	D	Dakota del Sur	Dakota del Sur	NR
Problema no disjunto	D	Dakota del Sur	Dakota del Sur	Dakota del Sur	Dakota del Sur
Problema de contención no configurado	D	Dakota del Sur	Dakota del Sur	Dakota del Sur	NR

Ejemplos:
Aquí, discutiremos algunos ejemplos para una mejor comprensión de la siguiente manera.

Ejemplo-1: 
{TM | Nº de estados en TM=2. } 
Solución –
Decidible ya que para esto tenemos que encontrar no. de Nodes en el gráfico.

Ejemplo-2: 
TM se detiene después de 100 movimientos.
Solución – 
Decidible ya que tenemos lógica tanto para ‘sí’ como para ‘no’. 

Yes : No string halts within 100 moves. (Check up to 100 length string).
No  : At least one string halts within 100 moves.

Ejemplo-3: 
TM se detiene en w después de 100 movimientos.
Solución: 
semidecidible, ya que tenemos lógica solo para ‘sí’ y ninguna lógica para ‘no’.

Yes : Halts after 100 moves has a logic.
No  : Doesn't halt after 100 moves have no logic as can go into an infinite loop or never halt.

Ejemplo-4: 
TM alcanza el estado q.
Solución: 
semidecidible, ya que tenemos lógica solo para ‘sí’ y ninguna lógica para ‘no’.

Yes : We have logic for yes as TM reaches state q we will come to know.
No  : No logic for no as TM can never reach state q or can fall into 
      an infinite loop before reaching q and will never come to know.

Ejemplo-5: 
considere cuando la gramática dada genera un lenguaje libre de contexto.
Solución: 
indecidible ya que no tenemos lógica para ‘Sí’, que la gramática dada genera CFL.