Strong Rice's Theorem

Strong Rice's Theorem

Easy Theory

4 года назад

5,817 Просмотров

Ссылки и html тэги не поддерживаются


Комментарии:

@AssemblyWizard
@AssemblyWizard - 05.08.2022 17:44

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

Ответить
@Daniellee121
@Daniellee121 - 13.04.2021 18:43

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?

Ответить
@chirudeepnamini
@chirudeepnamini - 06.08.2020 10:07

can you make a video solving some problems based on this theorem..

Ответить