0 votes 0 votes $D = \left \{ <M> \mid \ M \text{ is a TM that rejects the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable? Theory of Computation decidability + – Mk Utkarsh asked Sep 15, 2018 • edited Sep 16, 2018 by Mk Utkarsh Mk Utkarsh 513 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Balaji Jegan commented Sep 15, 2018 reply Follow Share D' = {M∣ M is a TM that doesn't reject the input string x} This I think is Undecidable(not even semi-decidable) as complement of Halting Problem can be reduced to D'. 0 votes 0 votes Mk Utkarsh commented Sep 15, 2018 i edited by Mk Utkarsh Sep 15, 2018 reply Follow Share Balaji i feel u are correct but you are also saying that D in this question is RE, but arjun sir said here that it is non RE. 0 votes 0 votes Arjun commented Sep 15, 2018 reply Follow Share Well what is the difference of this problem and "non-halting" problem? 0 votes 0 votes Balaji Jegan commented Sep 15, 2018 reply Follow Share Sir, From what I understood, Complement of Reject is not Reject(Which can include String getting Accepted or the string getting into Loop Forever) Not Halting refers to only String getting into Loop Forever. 0 votes 0 votes Arjun commented Sep 15, 2018 reply Follow Share @Balaji correct. So D is? 0 votes 0 votes Balaji Jegan commented Sep 15, 2018 reply Follow Share D is semi-decidable since Halting Problem can be reduced to D 0 votes 0 votes Arjun commented Sep 15, 2018 reply Follow Share No, D is semi-decidable. But when you reduce halting problem to $D$, $D$ only becomes "not-decidable" or undecidable. To say that $D$ is semi-decidable, you should give a mechanism to identify all strings in $D$ - this is straightforward here - we can know when $TM$ $M$ rejects the string $x.$ i.e., run the given $TM$ on input $x$, if $x$ is rejected, output "yes". If $x$ is accepted, output "no". If infinite loop, output also goes to "infinite loop". 0 votes 0 votes Mk Utkarsh commented Sep 16, 2018 reply Follow Share so sir when we reduce halting problem to some other problem D, D only becomes undecidable(it maybe or may not be semi-decidable). according to you D is semi-decidable? 0 votes 0 votes Arjun commented Sep 16, 2018 reply Follow Share yes, exactly. But $D$ here is semi-decidable as for strings in $L$ there is no chance of infinite looping for TM. 1 votes 1 votes Mk Utkarsh commented Sep 16, 2018 reply Follow Share Arjun thanks sir i think i have cleared most of my doubts. 1 votes 1 votes Please log in or register to add a comment.