Verificamos de forma cada uno de los enunciados de nuestra página web con la meta de mostrarte siempre información veraz y actualizada.
Solución:
Un idioma es reconocible si hay una máquina de Turing que se detendrá y aceptará solamente las cadenas en ese idioma y para las cadenas que no están en el idioma, la MT rechaza o no se detiene en absoluto. Nota: no es necesario que la máquina de Turing se detenga para cadenas que no estén en el idioma.
Un idioma es Decidible si hay una Máquina de Turing que aceptará cadenas en el idioma y rechazará cadenas que no estén en el idioma.
Quizás este enlace sea útil: http://kilby.stanford.edu/~rvg/154/handouts/decidability.html
Descargo de responsabilidad: Voy a elaborar sólo un poco.
Cuando se le da una entrada a una Turing Machine(TM), puede hacer una de estas tres cosas:
- Acepte la entrada alcanzando el estado de aceptación ($q_accept$).
- Rechace la entrada alcanzando el estado de rechazo ($q_reject$).
- Sigue computando para siempre. Esto se puede llamar un “bucle”.
Si la máquina sigue computando para siempre, consideramos que la máquina ha rechazado el string pero lo hace en un número infinito de pasos. Así, si la máquina acepta una string¡debe hacerlo en un número finito de pasos!
Un lenguaje de una máquina de Turing es simplemente el conjunto de todas las cadenas que son aceptadas por la máquina de Turing. En este caso, decimos que el Idioma es reconocido por la Máquina de Turing. Esto me lleva a la definición de un lenguaje reconocible de Turing:
Def : Un idioma se llama Turing reconocible si alguna máquina de Turing lo reconoce.
Ahora, considere una máquina de Turing $M$ y un idioma $L$ (sobre el alfabeto de entrada $Sigma$) que es reconocido por $M$. Por tanto, $L$ es un Lenguaje Turing Reconocible (ya que la TM $M$ lo reconoce). Considere el conjunto de cadenas que no están en $L$ (lo llamamos $overlineL$). Sabemos que la máquina $M$ no acepta estas cadenas. Entonces, cuando simulamos un string $w$ $in$ $overlineL$ en $M$, hay dos posibilidades:
- M termina en estado de rechazo ($q_reject$).
- M sigue computando para siempre (va en un “bucle”).
Si la máquina $M$ es tal que para todo $w$ $in$ $overlineL$, produce la salida al pasar al estado de rechazo, entonces tenemos una máquina de Turing ($M$) para $ L$ que tiene la propiedad de que, para cualquier entrada (sobre $Sigma^*$) ¡nunca entra en un bucle! Por lo tanto, podemos decir que para cualquier entrada (sobre $Sigma^*$), la Máquina de Turing $M$ decide si aceptar o rechazar la entrada en un número finito de pasos. La máquina $M$ se llama decisivo. Los lenguajes para los que podemos diseñar Máquinas de Turing con la propiedad anterior se denominan Turing decidible idiomas En el ejemplo anterior, decimos que $M$ decide $L$. Aquí está la definición:
Def : Un idioma se llama Turing decidible si alguna máquina de Turing decide eso.
Manteniéndolo simple: un idioma $L$ es Turing Decidible si algún decisivo $ millones $, decide eso.
Para obtener más información, puede consultar: Introducción a la teoría de la computación de Michael Sipser.
Mi respuesta está mayormente de acuerdo con la de Aryabhata:
Un idioma es “reconocible por Turing” si existe una máquina de Turing tal que
-
al encontrarse con un string en ese idioma, la máquina termina y acepta que string;
-
al encontrarse con un string no en ese idioma, la máquina termina y rechaza ese string o no termina en absoluto.
Un lenguaje es “Decidible por Turing” si existe una máquina de Turing tal que
-
al encontrarse con un string en ese idioma, la máquina termina y acepta que string;
-
al encontrarse con un string no en ese idioma, la máquina termina y rechaza ese string.
Tenga en cuenta que “Turing-Decidible” es una condición más fuerte que “Turing-Recognizable”, porque, si un idioma es Turing-Decidible, entonces su máquina de Turing correspondiente nunca funciona para siempre.