1679
правок
Изменения
→Теория вычислимости
*[[Перечислимые языки]]
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
*[[Вычислимые функции]]
*[[Диагональный метод]]
*[[Иммунные и простые множества]]
*[[Теорема о рекурсии]]
=== Вычислительные формализмы ===
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Линейный клеточный автомат, эквивалентность МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
=== Примеры неразрешимых задач ===
*[[m-сводимость]]
*[[Примеры неразрешимых задач: проблема соответствий Поста]]
*[[Примеры неразрешимых задач: задача о замощении]]
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ]]
*[[Теорема Райса-Шапиро]]
