[[Категория: Теория формальных языков]]
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
== Автоматы и регулярные языки ==
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
*[[ДМП-автоматы и неоднозначность]]
== Теория вычислимости ==
=== Разрешимые и перечислимые языки ===
*[[Разрешимые (рекурсивные) языки]]
*[[Перечислимые языки]]
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
*[[Вычислимые функции]]
*[[Вычислимые числа]]
*[[Универсальная функция|Универсальная функция и главные нумерации]]
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
*[[Неотделимые множества]]
*[[Иммунные и простые множества]]
*[[Теорема о рекурсии]]
*[[Квайны]]<tex> ^\star </tex>
*[[Busy beaver]]
*[[Колмогоровская сложность]]<tex> ^\star </tex>
=== Вычислительные формализмы ===
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]<tex> ^\star </tex>
*[[Рекурсивные функции, представимость в формальной арифметике | Примитивно рекурсивные функции]]<tex> ^\star </tex>
*[[Частично рекурсивные функции]]<tex> ^\star </tex>
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Линейный клеточный автомат, эквивалентность МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
*[[Линейный ограниченный автомат]]
*[[Сверхтьюринговые вычисления (гипервычисления)]]<tex> ^\star </tex>
*[[Тьюринг-полнота]]<tex> ^\star </tex>
=== Примеры неразрешимых задач ===
*[[m-сводимость]]
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Эквивалентность КС-грамматик]]
*[[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пустота пересечения КС-грамматик]]
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
*[[Неразрешимость исчисления предикатов первого порядка]]
*[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
*[[Неразрешимость задачи вывода типов в языке с зависимыми типами]]
*[[Игра «Жизнь»]]<tex>^\star</tex>
*[[Неразрешимость игры Braid]]<tex>^\star</tex>
*[[Теорема Райса-Шапиро]]
