CODEWITHSUNDEEP
computation-theoryturing-machinesautomaton
Andrew Fells
Andrew Fells

Reputation: 89

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).

Upvotes: 0

Views: 298

Answers (1)

Peter Leupold
Peter Leupold

Reputation: 1212

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.

Upvotes: 1

Related Questions