Si no hay reducción de A a B

Question

Estoy enfrentando la siguiente pregunta:

Si no hay $

Answer 1

El idioma $ a $ no es necesariamente indecidible si permitimos cualquier opción arbitraria pero fija de $ b $ . Por ejemplo, se establece $ b $ para ser el idioma vacío. El único idioma reducible para $ b $ es $ b $ it.

Por otro lado, si quiere decir que existe un idioma $ b $ de modo que $ a \ leq_m b $ , entonces, para cada idioma $ a $ sin importar si es decidible o no hay un contenedor de matemáticas "> $"> $ B $ , a saber, elija $ b $ para ser el idioma $ a $ mismo.

Tenga en cuenta que la única manera significativa de leer la declaración, es arreglar $ b $ a un idioma que está completo para la clase de idiomas decidibles. Claramente, los idiomas decidibles están cerrados en $ \ leq_m $ reducciones, sin embargo, no creo que se conoce un lenguaje completo para esta clase (o si un idioma puede ser dicho idioma construido). Sin embargo, para un idioma $ b $ , un idioma $ a $ es decidible si y solo si < span class="Math-contenedor"> $ A \ leq_m B $ por definición de lenguajes completos.