Теория вычислимости

Разрешимые и перечислимые языки

• Разрешимые (рекурсивные) языки
• Перечислимые языки
• Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
• Вычислимые функции
• Вычислимые числа
• Универсальная функция и главные нумерации
• Свойства перечислимых языков. Теорема Успенского-Райса
• Неотделимые множества
• Иммунные и простые множества
• Теорема о рекурсии
• Квайны[math] ^\star [/math]
• Busy beaver
• Колмогоровская сложность[math] ^\star [/math]

Вычислительные формализмы

• Машина Тьюринга
• Лямбда-исчисление[math] ^\star [/math]
• Примитивно рекурсивные функции[math] ^\star [/math]
• Частично рекурсивные функции[math] ^\star [/math]
• Стековые машины, эквивалентность двухстековой машины МТ
• Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
• Линейный клеточный автомат, эквивалентность МТ
• Возможность порождения формальной грамматикой произвольного перечислимого языка
• Линейный ограниченный автомат
• Сверхтьюринговые вычисления (гипервычисления)[math] ^\star [/math]
• Тьюринг-полнота[math] ^\star [/math]

Примеры неразрешимых задач

• m-сводимость
• Проблема соответствий Поста
• Однозначность КС-грамматики
• Эквивалентность КС-грамматик
• Пустота пересечения КС-грамматик
• Задача о замощении полимино
• Задача о выводе в полусистеме Туэ
• Неразрешимость исчисления предикатов первого порядка
• Неразрешимость проблемы существования решения диофантова уравнения в целых числах
• Неразрешимость задачи вывода типов в языке с зависимыми типами
• Игра «Жизнь»[math]^\star[/math]
• Неразрешимость игры Braid[math]^\star[/math]
• Теорема Райса-Шапиро