Es necesariamente el siguiente idioma no decidible

Question

Para a, B que no son decidibles, ¿no es necesariamente decidible?

Creo que la respuesta es no.No necesariamente. Pensé en el siguiente ejemplo, pero no refuta exactamente:

Si tomamos un y un complemento, y sin perder la generalidad, la palabra vacía está en una, que cada palabra en A "también está en AA 'u A'a, pero no puedo usarlo para mostrar que cada palabraEn A también está en AA 'u A'A.

Si alguien puede ayudarme, ¿cómo puedo demostrar que también está en AA 'u A'A se resolverá el problema?

Muchas gracias.

Answer 1

Tome algún idioma indecidable $ a $ y elija $ b= a '\ bigcup \ {\ epsilon \} $. $ b $ no es indecidible, y el resto de la prueba es así como lo que ya ha hecho.