mostra che questo set decidabile $ c $ esiste

Question

Mi sono imbattuto in questo problema che dice quello dato set disgiunti $ A $ e $ B $ St $ \ bar {A} $ e $ \ bar {b} $ sono entrambi calcolabili enumerabili (CE), esiste un set decidabile $ c $ st $ A \ SOTETTEQ C $ e $ c \ cap b=vuoto $ .

Penso che un modo per costruire $ c $ è quello di mostrare che $ \ bar {a} - \ bar {B} $ CE, ma è la differenza impostata $ \ bar {a} - \ bar {b} $ per questo caso particolare CE?

.

Answer 1

No, non è necessariamente enumerabile in modo ricorsivo.Ci sono lingue che sono ricorsivamente enumerabili ma non ricorsive.Pertanto, il loro complemento non è enumevole in modo ricorsivabile.Da ciò, dovresti essere in grado di dimostrare che la risposta alla domanda nella frase finale del tuo post è no (ti permetterò di compilare i dettagli da lì).