edited by
1,455 views
1 votes
1 votes
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$

What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
edited by

1 Answer

Best answer
3 votes
3 votes
As it stands, the question doesn't make sense. A language contains a set of strings, not a TM or a DFA or whatever.

So, the more appropriate question to ask would be to ask the properties of:

$$A_{TM} = \{<M,w> | \, \text{M is a TM which accepts w}\}$$

Now, we by the diagonalisation argument, we know that the given language is undecidable.

We can also prove it is Turing recognisable by creating a Universal TM which does the following:

1. Run the TM on the string $w$. If it ever enters its accept state, accept.
2. If it ever enters its reject, reject.

Thus, we've proven that $A_{TM}$ is both Turing Recognisable and undecidable.

Now, we also know that $L$ is decidable if and only if both $L$ and $L'$ are Turing recognisable.

Making use of this theorem, we can conclude that $\overline{A_{TM}}$ is not Turing recognisable because if it were, it would make $A_{TM}$ decidable.

I hope this helps.
selected by

Related questions

0 votes
0 votes
0 answers
1
Mk Utkarsh asked Sep 15, 2018
485 views
$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 recogn...
11 votes
11 votes
2 answers
2
sourav. asked Sep 9, 2017
4,370 views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...
2 votes
2 votes
2 answers
3
Akriti sood asked Jan 15, 2017
3,465 views
L={<M : M is a TM that accepts all even numbers }is it recursive/R.E??
1 votes
1 votes
1 answer
4
Xylene asked Jul 15, 2017
1,069 views
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?