0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ @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 $\endgroup$
    – akanxh2000
    Dec 27, 2020 at 18:29

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I had a similar approach to this, thanks for sharing. Is there a way to use diagonalization as it deals with the language of strings which do not belong in L(T) $\endgroup$
    – akanxh2000
    Dec 27, 2020 at 18:32

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.