Search code examples
formal-languagesdecidable

P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q

My problem: Define two sets P and Q of words (that is, two problems) such that: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q

Solution

  • One example of such sets:

    Define Q as the set of turing machines, which halt on empty input. Define P as the set of turing machines, which halt on every input.

    Clearly P ⊂ Q and P is undecidable and not semidecidable, but Q is undecidable and semidecidable.