Advertisement
Guest User

Untitled

a guest
Dec 13th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.82 KB | None | 0 0
  1. L_HALT: No. Rice's theorem only applies to languages containing Turing machines, but L_HALT contains pairs of Turing machines and inputs
  2.  
  3. L_emptyset: Yes. P = {\emptyset}
  4.  
  5. L_Sigma*: Yes. P = {\Sigma^*}
  6.  
  7. L_inf: Yes. P = {L | |L| is infinite}
  8.  
  9. L_epsilon-REJ: No. The intuition here is that whether or not M rejects the empty string tells you nothing about its language (the empty string could still be in L(M) if M accepts it or not in L(M) if M loops on it).
  10.  
  11. L_epsilon-ACC: Yes. P = {L | epsilon in L}
  12.  
  13. L_DEC: No. That M decides a language (i.e. halts on all inputs) does not tell you anything about L(M).
  14.  
  15. L_REC: No. First of all, L_REC is decidable since all Turing machines recognize a language, so Rice's theorem better not apply. As for why it doesn't apply: same reason as L_DEC.
  16.  
  17. L_UNREC: No. This should conform to your intuitions since "L(M) is unrecognizable" is a nonsensical statement. If L is a language of a Turing machine, then by definition it is recognizable, so in fact L_UNREC = \emptyset which is of course decidable. As for specifically why Rice's theorem doesn't apply: You could phrase L_UNREC as L_UNREC = {M | L(M) \in P} where P is the set of unrecognizable languages. However, recall that for Rice's Theorem to apply, P must be "non-trivial", meaning that it must contain at least one recognizable language and it must not contain at least one recognizable language. The set of unrecognizable languages by definition contains no recognizable languages so this P is trivial.
  18.  
  19. L_epsilon-LEFT: No. This is a language of Turing machines, but it has nothing to do with the language of those Turing machines. This is a "syntactic property" as opposed to a "semantic one". Moreover, you proved that a language almost exactly like this was decidable on HW4 (I think?), so it makes sense that Rice's theorem does not apply.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement