Undeciability

Question 1

When is a decision problem decidable? When is it semidecidable?

Answer 1

Question 2

What is the Halting problem? What is the universal Halting problem?

Answer 2

Question 3

What is the Theorem of Rice? Give a general description of its proof.

Answer 3

Question 4

Whatis the Post Correspondence Problem (PCP)?

Answer 4

Question 5

What is the modified PCP?

Answer 5

Question 6

Proof that it is undecidable if the intersection of two languages is the empty set.

Answer 6

Question 7

Proof that ambiguity of context-free grammars is undecidable.

Answer 7

Question 8

Proof that it is undecidable if a language contains a palindrome.

Answer 8