Комментарии:
Stronger Rice:
Sigma star not in P -> P not in RE
Sigma star in P -> P not in coRE
Empty set not in P -> P not in coRE
Empty set in P -> P not in RE
Cool takeaway: if the property P doesn't separate Sigma-star and empty-set (either both in P or both not in P), then the language is neither in RE nor in coRE
Thanks for the video. Just a quick question though: I know that A_TM is undecidable. Is the complement of undecidable not-recognizable? Why is that?
Ответитьcan you make a video solving some problems based on this theorem..
Ответить