1632
правки
Изменения
м
rollbackEdits.php mass rollback
=== Разрешимые и перечислимые языки ===
# [[Разрешимые (рекурсивные) языки]]
# [[Перечислимые языки]] 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>
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]0.5</li># поправить тех# добавить см также# добавить источники информации<li> [[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пустота пересечения КС-грамматик]] 0.5 </li># поправить тех
<li> [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] </li>
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
<li> [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]] (10) </li>
# дописать, чтобы было классно
<li> [[Неразрешимость задачи вывода типов в языке с зависимыми типами]] (3)</li>
# <tex>\beta</tex>-эквивалентны в интервики
# добавить пару примеров вывода типа в данной системе
<li> [[Игра «Жизнь»]] </li>
<li> [[Неразрешимость игры Braid]] </li>
<li> [[Теорема Райса-Шапиро]] </li>
</ol>
