Теория вычислимости:Тикеты — различия между версиями
(→Вычислительные формализмы) |
(→Разрешимые и перечислимые языки) |
||
| Строка 2: | Строка 2: | ||
=== Разрешимые и перечислимые языки === | === Разрешимые и перечислимые языки === | ||
# [[Разрешимые (рекурсивные) языки]] | # [[Разрешимые (рекурсивные) языки]] | ||
| − | # [[Перечислимые языки]] | + | # [[Перечислимые языки]] 0.5 |
| − | # [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] | + | ## добавить см также |
| − | # [[Вычислимые функции]] | + | # [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] 0.5 |
| − | # [[Вычислимые числа]] | + | ## поправить тех |
| + | # [[Вычислимые функции]] 0.5 | ||
| + | ## добавить см также | ||
| + | # [[Вычислимые числа]] 0.5 | ||
| + | ## поправить тех | ||
# [[Универсальная функция]] | # [[Универсальная функция]] | ||
| − | # [[Свойства перечислимых языков. Теорема Успенского-Райса]] | + | # [[Свойства перечислимых языков. Теорема Успенского-Райса]] 0.5 |
| + | ## поправить тех и псевдокод | ||
# [[Неотделимые множества]] | # [[Неотделимые множества]] | ||
| + | ## поправить тех | ||
| + | ## добавить см также | ||
# [[Иммунные и простые множества]] | # [[Иммунные и простые множества]] | ||
| − | # [[Теорема о рекурсии]] | + | # [[Теорема о рекурсии]] 0.5 |
| − | # [[Квайны]] | + | ## поправить псевдокод |
| − | # [[Busy beaver]] | + | ## поправить тех |
| + | ## сделать см также на проверяемые конспекты | ||
| + | # [[Квайны]] 0.5 | ||
| + | ## поправить псевдокод | ||
| + | ## добавить см также | ||
| + | # [[Busy beaver]] 0.5 | ||
| + | ## поправить псевдокод | ||
# [[Колмогоровская сложность]] | # [[Колмогоровская сложность]] | ||
| + | ## поправить всевдокод | ||
=== Вычислительные формализмы === | === Вычислительные формализмы === | ||
Версия 00:16, 3 июня 2018
Содержание
3. Теория вычислимости
Разрешимые и перечислимые языки
- Разрешимые (рекурсивные) языки
- Перечислимые языки 0.5
- добавить см также
- Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций 0.5
- поправить тех
- Вычислимые функции 0.5
- добавить см также
- Вычислимые числа 0.5
- поправить тех
- Универсальная функция
- Свойства перечислимых языков. Теорема Успенского-Райса 0.5
- поправить тех и псевдокод
- Неотделимые множества
- поправить тех
- добавить см также
- Иммунные и простые множества
- Теорема о рекурсии 0.5
- поправить псевдокод
- поправить тех
- сделать см также на проверяемые конспекты
- Квайны 0.5
- поправить псевдокод
- добавить см также
- Busy beaver 0.5
- поправить псевдокод
- Колмогоровская сложность
- поправить всевдокод
Вычислительные формализмы
- Машина Тьюринга
- Лямбда-исчисление
- Примитивно рекурсивные функции
- Частично рекурсивные функции
- Стековые машины, эквивалентность двухстековой машины МТ
- Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
- Линейный клеточный автомат, эквивалентность МТ
- Возможность порождения формальной грамматикой произвольного перечислимого языка
- Линейный ограниченный автомат
- Сверхтьюринговые вычисления (гипервычисления)
- Тьюринг-полнота (4)
- Провести аналогию с теоремой Геделя о неполноте
Примеры неразрешимых задач
- m-сводимость
- Проблема соответствий Поста
- Однозначность КС-грамматики
- Неразрешимость задачи об эквивалентности КС-грамматик
- Пустота пересечения КС-грамматик
- Задача о замощении полимино
- Задача о выводе в полусистеме Туэ
- Неразрешимость исчисления предикатов первого порядка
- Неразрешимость проблемы существования решения диофантова уравнения в целых числах (10)
- дописать, чтобы было классно
- Неразрешимость задачи вывода типов в языке с зависимыми типами (3)
- -эквивалентны в интервики
- добавить пару примеров вывода типа в данной системе
- Игра «Жизнь»
- Неразрешимость игры Braid
- Теорема Райса-Шапиро
