Terms Flashcards
When can rice’s theorem not be used?
It cannot be used when referring to properties about the machine.
What can rices theorem tell you about a language that is in D?
Nothing.
How many languages are not in SD?
Unaccountably infinite languages
Given a TM M is it decidable whether it is minimal?
No. It is not even semi-undecidable
When working with SD languages we cannot use what on our oracle?
the negation cannot be used because we cannot negate something we don’t know will halt
Decidable. Examine <M>, the string description of M, and determine whether that string is of
even length.</M>
~SD. We would need to try an infinite number of of strings.
SD/D. We need to detect that M halts and rejects (instead of looping which cannot be detected) which can be detected by simulation.
“Is M a deciding machine” decidable?
That question is equivalent to asking whether M halts on all inputs, which is not semi-decidable.
Proof for:
D, SD/D, or not in SD?
~SD. It would require an infinite computation.
Regular languages are closed under what?
Complement, Intersection, Difference, Reverse and Letter Substitution
CFC grammars are closed under what?
Union, Concatenation, Kleene Star, Reverse, and Letter Substitution
Is TILES in D, SD/D or ~SD? What about ~Tiles?
Tiles is in ~SD
~Tiles is in SD/D.
Is PCP in D, SD/D or ~SD? What about ~PCP?
PCP is in SD
~PCP is in ~SD
Can {a} be reduced to H?
Yes:
D, SD/D or ~SD?
~SD.
The language is asking if Ma halts on epsilon and Mb does not halt on epsilon.
D, SD/D or ~SD?
~SD.
