Search code examples
computation-theoryturing-machinesautomaton

Proof semidecidable languages

I have to proof "Semidecidable languages are closed by the direct morphism operation"

I think that a direct morphism from E to F is a pair of morphisms s: E -> F, p: F->E, with p · s = IdE.

So my porposal is make a proof with Turing Machines because Turing-Recognizable languages are closed under ∪, °, *, and ∩ but i dont know how to proof it with a specific language that runs in the TM (if my proposal is correct).

Solution

  • As your language L is semidecidable, there exists a Turing Machine TML that stops on every input that is in E. You want a machine TMK for the language K = s(L).

    1. On input w\in F* compute v = p(w) which is in E*.
    2. Simulate TML(v). If w\in s(L) then v\in L and the machine accepts.