Register

decidability doubt

• retagged by
656 views
0 0 votes
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems??

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · TIFR CSE 2017 | Part...Next → · Madeeasy Test Series
← Previous in category · TIFR CSE 2017 | Part...Next in category → · Regular Languages
Position:
Show:

Related questions

0 0 votes
1 1 answer
1.5k
1.5k views
ajaysoni1924 asked Jul 15, 2019
1,512 views
Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \ri...
0 0 votes
0 0 answers
701
701 views
Mk Utkarsh asked Nov 23, 2018
701 views
Decidability Doubt
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$$L_2 = \{ \text{<M>} | \ \text{M is a TM,...
0 0 votes
0 0 answers
551
551 views
aditi19 asked Oct 29, 2018
551 views
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
1 1 vote
2 2 answers
1.1k
1.1k views
rahul sharma 5 asked Jan 15, 2017
1,058 views
Doubt in GateCse Decidability Blog
In the deciadability chart mentioned on http://gatecse.in/grammar-decidable-and-undecidable-problems/The undecidable problems mentioned here are semidecidable(RE but not ...