Просмотр исходного текста страницы Производящие функции:Тикеты

== 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> взяли [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] 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>