Производящие функции:Тикеты — различия между версиями
(→Разрешимые и перечислимые языки) |
(→Вычислительные формализмы) |
||
| Строка 42: | Строка 42: | ||
<ol> | <ol> | ||
<li value="14">[[Машина Тьюринга]] </li> | <li value="14">[[Машина Тьюринга]] </li> | ||
| − | <li> [[Лямбда-исчисление]] 0.5</li> | + | <li> взяли [[Лямбда-исчисление]] 0.5</li> |
# Поправить тех | # Поправить тех | ||
| − | <li>[[Примитивно рекурсивные функции]] 0.5 </li> | + | <li> взяли [[Примитивно рекурсивные функции]] 0.5 </li> |
# Поправить тех | # Поправить тех | ||
<li> [[Частично рекурсивные функции]] </li> | <li> [[Частично рекурсивные функции]] </li> | ||
| − | <li> [[Стековые машины, эквивалентность двухстековой машины МТ]] 0.5 </li> | + | <li> взяли [[Стековые машины, эквивалентность двухстековой машины МТ]] 0.5 </li> |
# Добавить см также | # Добавить см также | ||
| − | <li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] 0.5 </li> | + | <li> взяли [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] 0.5 </li> |
# Добавить см также | # Добавить см также | ||
# поправить тех | # поправить тех | ||
| − | <li> [[Линейный клеточный автомат, эквивалентность МТ]] 0.5 </li> | + | <li> взяли [[Линейный клеточный автомат, эквивалентность МТ]] 0.5 </li> |
# добавить см также | # добавить см также | ||
| − | <li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] 0.5 </li> | + | <li> взяли [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] 0.5 </li> |
# поправить тех | # поправить тех | ||
<li> [[Линейный ограниченный автомат]]</li> | <li> [[Линейный ограниченный автомат]]</li> | ||
| − | <li> [[Сверхтьюринговые вычисления (гипервычисления)]] 0.5</li> | + | <li> взяли [[Сверхтьюринговые вычисления (гипервычисления)]] 0.5</li> |
# увеличить дроби | # увеличить дроби | ||
| − | <li> [[Тьюринг-полнота]] (4)</li> | + | <li> взяли [[Тьюринг-полнота]] (4)</li> |
# Провести аналогию с теоремой Геделя о неполноте | # Провести аналогию с теоремой Геделя о неполноте | ||
</ol> | </ol> | ||
Версия 22:19, 9 марта 2019
Содержание
1 Производящие функции
- Производящая функция
- Арифметические действия с формальными степенными рядами
- Производящие функции нескольких переменных
- Разложение рациональной функции в ряд
- Задача о счастливых билетах
- Произведение Адамара
- Интегрирование/дифференцирование производящих функций
- Производящая функция Дирихле
2 Теория вычислимости
Разрешимые и перечислимые языки
- Разрешимые (рекурсивные) языки
- взяли Перечислимые языки 0.5
- добавить см также
- взяли Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций 0.5
- поправить тех
- взяли Вычислимые функции 0.5
- добавить см также
- взяли Вычислимые числа 0.5
- поправить тех
- Универсальная функция
- Свойства перечислимых языков. Теорема Успенского-Райса 0.5
- поправить тех и псевдокод
- Неотделимые множества
- поправить тех
- добавить см также
- Иммунные и простые множества
- Теорема о рекурсии 0.5
- поправить псевдокод
- поправить тех
- сделать см также на проверяемые конспекты
- Квайны 0.5
- поправить псевдокод
- добавить см также
- Busy beaver 0.5
- поправить псевдокод
- Колмогоровская сложность 0.5
- поправить всевдокод
Вычислительные формализмы
- Машина Тьюринга
- взяли Лямбда-исчисление 0.5
- Поправить тех
- взяли Примитивно рекурсивные функции 0.5
- Поправить тех
- Частично рекурсивные функции
- взяли Стековые машины, эквивалентность двухстековой машины МТ 0.5
- Добавить см также
- взяли Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ 0.5
- Добавить см также
- поправить тех
- взяли Линейный клеточный автомат, эквивалентность МТ 0.5
- добавить см также
- взяли Возможность порождения формальной грамматикой произвольного перечислимого языка 0.5
- поправить тех
- Линейный ограниченный автомат
- взяли Сверхтьюринговые вычисления (гипервычисления) 0.5
- увеличить дроби
- взяли Тьюринг-полнота (4)
- Провести аналогию с теоремой Геделя о неполноте
Примеры неразрешимых задач
- m-сводимость
- Проблема соответствий Поста
- Однозначность КС-грамматики
- Неразрешимость задачи об эквивалентности КС-грамматик 0.5
- поправить тех
- добавить см также
- добавить источники информации
- Пустота пересечения КС-грамматик 0.5
- поправить тех
- Задача о замощении полимино
- Задача о выводе в полусистеме Туэ
- Неразрешимость исчисления предикатов первого порядка
- Неразрешимость проблемы существования решения диофантова уравнения в целых числах (10)
- дописать, чтобы было классно
- Неразрешимость задачи вывода типов в языке с зависимыми типами (3)
- -эквивалентны в интервики
- добавить пару примеров вывода типа в данной системе
- Игра «Жизнь»
- Неразрешимость игры Braid
- Теорема Райса-Шапиро
