## теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)
# [[Busy beaver]]
---- *# [[Машина Тьюринга]]*# [[Лямбда-исчисление]]*# [[Примитивно рекурсивные функции]]*## названия функций надо в \mathrm или \mathtt## привести пример использования теоремы о примитивной рекурсивности# [[Частично рекурсивные функции]]*## англоязычные термины## [[Стековые машины, эквивалентность двухстековой машины МТ]]*# [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]*# [[Линейный клеточный автомат, эквивалентность МТ]]*# [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]## внутренние ссылки=== Примеры неразрешимых задач ===## категории*# '''!!!''' [[m-сводимость]]*## англоязычные термины## ссылка на английскую википедию, у существующих источников ссылки на номер страницы## написать еще про сведение по Тьюрингу и чем m-сведение от него принципиально отличается. Написать, что произойдет, если использовать программы с оракулом, который разрешает задачу останова, написать про иерархию Тьюринга# '''!!!''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]*## англоязычные термины## {{tick}} англоязычные источники, в частности, википедия## {{tick}} Выполним m-сведение множества пар из машины Тьюринга (МТ) и строки w , где M(w) не зависает — у этого множества есть название## {{tick}} "Договоримся, что состояния в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?## {{tick}} "можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо## {{tick}} побольше интервики## {{tick}} форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.## {{tick}} Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.## вообще в целов привести к более адекватному и понятному виду# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]*# '''взяли''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]*## замечания в обсуждении# '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]*## замечения в обсуждении# '''!!!''' [[Неразрешимость исчисления предикатов первого порядка]]*## написать. Это очень просто на самом деле, если немного помнить матлогику# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.*# [[Теорема Райса-Шапиро]]
