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