Разрешимые (рекурсивные) языки

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Язык [math]L[/math] называется разрешимым (рекурсивным), если существует такая программа [math] p [/math], что [math] \forall w \in L: p(w) = 1[/math] и [math] \forall w \notin L: p(w) = 0[/math].


Примеры

Пример разрешимого множества

Пример неразрешимого множества