Register

TM that rejects input string x

• edited by
513 views
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?
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Mk Utkarsh asked Sep 15, 2018
1,506 views
TM that accepts input string x
$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?
$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 recogni...
User Avatar
11 votes
11 votes
2 answers
2
sourav. asked Sep 9, 2017
4,532 views
$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$
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...
User Avatar
8 votes
8 votes
3 answers
3
Akriti sood asked Dec 16, 2016
4,900 views
L= {<TM> | TM halts on every input}
$L=\left \{ <TM> | TM\ halts\ on\ every\ input\ \right \}$ is above language Recursively enumerable or non recursively enumerable??
$L=\left \{ <TM | TM\ halts\ on\ every\ input\ \right \}$is above language Recursively enumerable or non recursively enumerable??
User Avatar
2 votes
2 votes
2 answers
4
Akriti sood asked Jan 15, 2017
3,533 views
L={<M> : M is a TM that accepts all even numbers }
L={<M> : M is a TM that accepts all even numbers } is it recursive/R.E??
L={<M : M is a TM that accepts all even numbers }is it recursive/R.E??
User Avatar
Link Copied!