I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {0,1}^* of all Turing machines which at least halts on at least one input x (might also accept it) and produce the output 0.

In my opinion, this language is semi-decidable because to me, it looks like a modified version of the Halting problem. My way of showing that this language is semi-decidable would be by using a Universal Turing machine which takes an input of the form w#x where w is the encoding of a TM and x the inputs that M_w take. The problem is I am not really sure if I am on the right track, the language is semi-decidable at all, and also not really sure if the Universal Turing machine is the right way to show the A semi-decidable is. I really do not have any experience working with Universal Turing machines, saw only 1 or 2 problems online using it. How can I prove it?

Extra question: Am I wrong for thinking that this language is Undecidable? We can prove it by many to one reduction of the Halting problem on the empty string(which is undecidable) to the Language A.


1 Answer 1


Since it seems like you are really uncertain about your own solution. Let's verify it step by step:

1- A is undecidable.

To prove this statement, it is enought to show that there is a mapping reduction from the following set to A:

Halt = { | M is a Turing machine which halts on }

For any Turing machine M, we define M' as:

For input w:

1- Run M on .

2- Give 0 as output.

It is pretty clear that M' belongs to A if and only if M belongs to Halt.

By undecidability of Halt, A is also undecidable.

2- A is semi-decidable.

To prove this. Consider the following set:

AMAI = {<M,w,s> | M,w and s belong to N}

We can make an enumerater to enumerate all members of AMAI. We use this enumerater to enumerate A as well:

For each <M,w,s>:

1- Run M on w by s computational steps of M.

2- If M halts on w in at most s computational steps and M gives 0 as output, print <M,w>.

So A is semi-decidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.