Изменения

== 1 Производящие функции ==# взяли [[Производящая функция]] 0,5## См. также добавить# взяли [[Арифметические действия с формальными степенными рядами]] 0.5## "(a0+a1s+a2s2+⋯+ak−1sk−1sk" забыта скобка# взяли [[Производящие функции нескольких переменных]] 0.5## Заменить дефис на тире, там где должно быть тире

# взяли [[Задача о счастливых билетах]] 0.5## Поправить тех# взяли [[Произведение Адамара рациональных производящих функций|Произведение Адамара]] 0.5## Поместить все цифры в тех (в заголовках)

# взяли [[Производящая функция Дирихле]] 3 == 2 Теория вычислимости ===== Разрешимые и перечислимые языки ===# [[Разрешимые (рекурсивные) языки]]# взяли [[Перечислимые языки]] 0.5 ## добавить см также# взяли [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] 0.5## поправить тех# взяли [[Вычислимые функции]] 0.5## добавить см также# взяли [[Вычислимые числа]] 0.5## поправить тех# [[Универсальная функция]] # [[Свойства перечислимых языков. Теорема Успенского-8Райса]] 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"Attention! Можно привести доказательство теоремы > [[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>