Теория вычислимости:Тикеты — различия между версиями
(→Вычислительные формализмы) |
(→Примеры неразрешимых задач) |
||
| Строка 36: | Строка 36: | ||
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li> | <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li> | ||
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li> | <li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li> | ||
| + | <li> [[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пустота пересечения КС-грамматик]] </li> | ||
<li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li> | <li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li> | ||
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li> | <li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li> | ||
| Строка 41: | Строка 42: | ||
<li> [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]] (10) </li> | <li> [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]] (10) </li> | ||
# дописать, чтобы было классно | # дописать, чтобы было классно | ||
| + | <li> [[Неразрешимость задачи вывода типов в языке с зависимыми типами]] (3)</li> | ||
| + | # <tex>\beta</tex>-эквивалентны в интервики | ||
| + | # добавить пару примеров вывода типа в данной системе | ||
<li> [[Игра «Жизнь»]] </li> | <li> [[Игра «Жизнь»]] </li> | ||
<li> [[Неразрешимость игры Braid]] </li> | <li> [[Неразрешимость игры Braid]] </li> | ||
<li> [[Теорема Райса-Шапиро]] </li> | <li> [[Теорема Райса-Шапиро]] </li> | ||
</ol> | </ol> | ||
Версия 22:24, 19 мая 2017
Содержание
3. Теория вычислимости
Разрешимые и перечислимые языки
- Разрешимые (рекурсивные) языки
- Перечислимые языки
- Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
- Вычислимые функции
- Вычислимые числа
- Универсальная функция
- Свойства перечислимых языков. Теорема Успенского-Райса
- Неотделимые множества
- Иммунные и простые множества
- Теорема о рекурсии
- Квайны
- Busy beaver
- Колмогоровская сложность
Вычислительные формализмы
- Машина Тьюринга
- Лямбда-исчисление
- Примитивно рекурсивные функции
- Частично рекурсивные функции
- Стековые машины, эквивалентность двухстековой машины МТ
- Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
- Линейный клеточный автомат, эквивалентность МТ
- Возможность порождения формальной грамматикой произвольного перечислимого языка
- Линейный ограниченный автомат
- Сверхтьюринговые вычисления (гипервычисления)
- Тьюринг-полнота
Примеры неразрешимых задач
- m-сводимость
- Проблема соответствий Поста
- Однозначность КС-грамматики
- Неразрешимость задачи об эквивалентности КС-грамматик
- Пустота пересечения КС-грамматик
- Задача о замощении полимино
- Задача о выводе в полусистеме Туэ
- Неразрешимость исчисления предикатов первого порядка
- Неразрешимость проблемы существования решения диофантова уравнения в целых числах (10)
- дописать, чтобы было классно
- Неразрешимость задачи вывода типов в языке с зависимыми типами (3)
- -эквивалентны в интервики
- добавить пару примеров вывода типа в данной системе
- Игра «Жизнь»
- Неразрешимость игры Braid
- Теорема Райса-Шапиро
