# Is the decision problem, for a Turing Machine are there any input strings rejected decidable?

Given a Turing Machine T, are there any input strings rejected by T. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it.

My initial approach would be to reduce the Halting Problem as either a string will 1)halt on final state i.e accepted or 2)halt on non-final state and go in a loop

Perhaps, there is another approach involving diagonalization where I can prove that the diagonalization language is finite - how do I do that?

• @BaderAbuRadi I believe it does as checking if input strings are rejected by T implicitly involves checking if L(T) = Σ∗. Although I wanted to know the possible approaches in my case Dec 27, 2020 at 18:29

Let us start by properly defining your language as say $$L = \{\langle M \rangle \mid M \text{ rejects some input } x \in \Sigma^\ast\}$$ where $$\langle \cdot \rangle$$ denotes some suitable encoding over our alphabet $$\Sigma$$. To reduce $$L$$ to the halting problem $$\mathrm{Halt} = \{\langle M, w \rangle \mid M \text{ halts on } w\}$$ we consider some $$\mathrm{Halt}$$ instance consisting of a TM $$M$$ and some input $$w$$ and define a new TM $$M_w$$ which always, no matter what input it is given, just simulates the behavior of $$M$$ on $$w$$ with the slight change that it rejects if $$M$$ accepts, i.e. $$M_w$$ rejects precisely if $$M$$ halts on $$w$$ and does not halt if $$M$$ does not halt on $$w$$. Note that $$M_w$$ can be algorithmically constructed from $$M$$ and $$w$$.
We see that $$\langle M, w \rangle \in \mathrm{Halt}$$ if and only if $$\langle M_w \rangle \in L$$, i.e. we have shown that the halting problem reduces to $$L$$ and thus $$L$$ is undecidable. However, $$L$$ is also recursively enumerable: Fix some ordering of $$\Sigma^\ast$$ and iteratively execute $$M$$ on the first $$n$$ strings of $$\Sigma^\ast$$ for $$n$$ steps. If $$M$$ rejects some string in $$\Sigma^\ast$$, this procedure will detect it in finitely many steps, showing that $$L$$ is semi-decidable and hence recursively enumerable.