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