# Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

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

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.