1679
правок
Изменения
Нет описания правки
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
__TOC__
== 1. Автоматы и регулярные языки ==
# '''взяли !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
## написать
# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
== 3. Теория вычислимости ==
# [[Разрешимые (рекурсивные) языки]]
# [[Перечислимые языки]]
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
# [[Вычислимые функции]]
# [[Вычислимые числа]]
# [[Диагональный метод]]
# [[Свойства перечислимых языков. Теорема Успенского-Райса]]
# [[Главные нумерации]]
# [[Неотделимые множества]]
# [[Иммунные и простые множества]]
# [[Теорема о рекурсии]]
# [[Busy beaver]]
----
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]
*[[Примитивно рекурсивные функции]]
*[[Частично рекурсивные функции]]
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Линейный клеточный автомат, эквивалентность МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
=== Примеры неразрешимых задач ===
*[[m-сводимость]]
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
*[[Неразрешимость исчисления предикатов первого порядка]]
*[[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
*[[Теорема Райса-Шапиро]]
