Todos los problemas relacionados con las máquinas de Turing que involucran únicamente el lenguaje que acepta la MT son indecidibles

Question

Me encontré con la siguiente declaración en el texto clásico "Introducción a la teoría, los lenguajes y la computación de los autómatas" de Hopcroft, Ullman, Motwani.

All problems about Turing machines that involve only the language that the TM accepts are undecidable

Dicen que el teorema anterior es según el teorema de Rice que establece que:

"Todas las propiedades no triviales de los lenguajes RE son indecidibles".

¿En qué son equivalentes estas dos afirmaciones?Las primeras ofertas sólo problemas mientras que el último se ocupa de propiedad no trivial.

Answer 1

Hay algunas palabras clave en el extracto de dicho libro de texto: no trivial, problema, propiedad.

Ahora bien, ¿qué es un problema, asumiendo que no estamos tratando con problemas de optimización combinatoria, es decir?Estamos tratando sólo con preguntas que tienen una respuesta SÍ o NO.Cuando hace una pregunta SÍ o NO a una cadena de entrada, si la respuesta es SÍ, la coloca en un conjunto $l$ y si la respuesta es NO simplemente la descartas.Ahora este conjunto $l$ es el idioma o el problema.Contiene todas aquellas cadenas que satisfacen nuestra pregunta de SÍ o NO.

Todo no trivial problemas acerca de máquinas de turing que involucran sólo el idioma que acepta la MT son indecidibles

Aquí el autor está hablando de preguntas SÍ o NO (con respecto a las máquinas de Turing) que sólo involucran la Lenguaje que acepta la máquina de Turing.,es decir.el lenguaje enumerable recursivamente (RE), lo que significa que nuestro conjunto de "problemas" contendrá sólo lenguajes RE.Ahora bien, un problema trivial es aquel en el que nuestra pregunta de SÍ o NO se satisface con todas las entradas o con ninguna de las entradas.Entonces, un problema no trivial es aquel que no está vacío ni tiene todas las entradas posibles.

Teorema del arroz:"Todas las propiedades no triviales de los lenguajes RE son indecidibles".

La propiedad de los lenguajes RE es un conjunto de lenguajes RE que tienen dicha propiedad.

Propiedad no trivial:La propiedad se cumple con todos los idiomas interesados ​​o con ninguno.

Entonces, la "propiedad no trivial de los lenguajes RE" se convierte en el conjunto de lenguajes RE y no está vacía ni tiene todos los lenguajes RE posibles.

Por el argumento anterior podemos decir que las dos afirmaciones son equivalentes.

(De hecho, propiedad y problema son la misma cosa; después de todo, ambos son un conjunto de cadenas.Ahora podríamos pensar que la propiedad es un conjunto de idiomas, aunque si bien es cierto, es inconveniente representar idiomas en un conjunto (ya que los idiomas pueden ser infinitamente largos), más bien lo que se hace es que en lugar del idioma, representamos el correspondiente. Máquina de Turing con una codificación adecuada)