Rec e re sotto l'incrocio

Question

L'intersezione di un linguaggio ricorsivo e un linguaggio ricorsivamente enumarabile sarebbero ricorsivi o ricorrentemente enumbarbabili o nessuno dei due?

Assumere $ L_ {3} $ è l'intersezione di qualche linguaggio $ L_ {1} $ $ epsilon $ Re e qualche altra lingua $ L_ {2} $ $ epsilon $ Rec.

Da $ L_ {2} $ $ epsilon $ Rec, ci deve essere una macchina da turing $ M_ {2} $ che mantiene ogni input, quando o meno l'ingresso x $ epsilon $ $ L_ {2} $. Se ora abbiamo un K-NTM $ M_ {3} $ che su una band simula$ M_ {2} $ e dopo l'accettazione dell'ingresso passa a un'altra banda dove poi simula $ M_ {1} $ (per $ L_ {1} $).

Da $ M_ {1} $ è sempre simulato se $ M_ {2} $ accetta l'input, $ M_ {1} $ ha solo la possibilità di trattenere ogni parola x $ epsilon $ $ L_ {1} $ $ bigcap $ $ L_ {2} $.

Ciò significa che possiamo già supporre che non rimarremo bloccati in un ciclo per le parole x $ notin $ $ L_ {2} $.

Tuttavia non è il caso delle parole che si trovano nell'intersezione o solo in $ L_ {2} $ e non in $ L_ {1} $, come simulazione di $ M_ {1} $ Sarai anche in modo ricorsivo e potrà funzionare per sempre, senza che noi non sappia mai se l'input è accettato o meno.

Se i miei pensieri finora fossero corretti, ciò significa che $ L_ {3} $ $ epsilon $ RIF.

Ciò di cui sono incerto è se c'è qualche tipo di algoritmo o tecnica con cui potremmo fare la simulazione di $ M_ {1} $ decidabile, o se forse è possibile creare una TM completamente nuova, indipendente da $ M_ {1} $ e $ M_ {2} $ E assicurarsi che sia decidibile?