Изменения
Нет описания правки
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
*[[Лемма Огдена]]
*[[Существенно неоднозначные языки]]
== Теория Вычислимости ==
*[[Разрешимые (рекурсивные) языки]]
*[[Перечислимые языки]]
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
*[[Разрешимость перечислимого и коперечислимого языка]]
*[[Вычислимые функции]]
*[[Диагональный метод. Невозможность одновременного существования универсальной функции и всюду определенности всех элементов семейства вычислимых функций]]
*[[Характеристика перечислимых множеств через вычислимые функции]]
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
*[[Главные нумерации]]
*[[Неотделимые множества]]
*[[Имунные и простые множества]]
*[[Теорема о рекурсии]]
