Question

Let C be a language. Prove that C is Turing-recognizable if a decidable language D exists such that .

Short answer

It can be proved that that C is Turing-recognizable if a decidable language D exists such that .

Step-by-step solution

Explain Decidable language

A language is said to be decidable if the input of a language is accepted by a Turing machine.

Step 2: Prove that C is Turing-recognizable

Consider that the language C is recognized by the Turing machine M and consider that an input x is given to the Turing machine.

The language D on input verifies whether the y decides an accepting computation of the input string x on the machine M.

Consider, that the D is a decider.

Construct the Turing machine that decides the decidability of the C. Construct the Turing machine that searches y and find it.

The given string is tested using the constructed Turing machine.

If the Turing machine accepts, otherwise rejects.

Therefore, it can be proved that that C is Turing-recognizable if a decidable language D exists such that .