Register

decidability

291 views
0 votes
0 votes

So my doubt is it is a problem from a document given on http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples but i m not able to understand their ideas to prove decidable/semidecidable/undecidable so i m ploadinng one problem from there so if somone is able 2 understand then plzz explain bcoz i almost all problems they are using sme idea ie. reduction from halting problem or its complement 
link of source is http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf 
   

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

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
149 views
Michael Sipser Decidability Problem
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. L = {M | M is a Turing machine and L(M) ∈ TIME(2^n)}
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
User Avatar
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
148 views
Michael Sipster Decidability Problems
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
User Avatar
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
152 views
Decidability and undecidability
How is equality problem for DCFL decidable?
How is equality problem for DCFL decidable?
User Avatar
Link Copied!