1679
правок
Изменения
→3. Теория вычислимости
== 3. Теория вычислимости ==
# [[Разрешимые (рекурсивные) языки]]
## англоязычные термины
## категории
## ссылки на википедию, русскую и английскую
# [[Перечислимые языки]]
## англоязычные термины
## ссылки на википедию
## написать про классы RE, R, co-RE.
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
# [[Вычислимые функции]]
## англоязычные термины
## ссылки на википедию
# [[Вычислимые числа]]
# '''!!!''' [[Диагональный метод]] ## объяснить, что такое универсальная функция неформально, и нафига она нужна. ## англоязычные термины ## внутренние ссылки## нужны ссылки на литературу и статьи, особенно на англоязычные. В уже существующем русском источнике не указан номер конкретной страницы, например ## непонятно, где, собственно, возникает диагональ, надо это показать ## также статья называется как-то глупо, лучше назвать ее "Универсальная функция" ## см. замечания для главных нумераций## категорию проставить
# [[Свойства перечислимых языков. Теорема Успенского-Райса]]
## классы языков в mathrm
## заголовки верхнего уровня в ==, а не =
## англоязычные термины
## категорию проставить
## ссылки на вики
# [[Главные нумерации]]
## см. "Диагональный метод"
## во-первых, тут какая-то муть
## во-вторых, тут копипаста из Шеня, кажется
## в третьих тут наполовину совпадает с "Диагональным методом". Короче их надо смержить и нормально написать.
## ну и надо написать, зачем вообще нужны эти главные нумерации
# [[Неотделимые множества]]
## английские источиники и термины
## нормально оформить уже существующий источник
## написать, зачем оно может пригодиться
# [[Иммунные и простые множества]]
# # английские источиники и термины## ссылки на вики## а зачем оно нужно?# '''!!!''' [[Теорема о рекурсии]]## во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские) ## дать ссылки на английские источники и термины ## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. ## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. # '''!!!''' [[Теорема о рекурсии]]#: Добавить примеры простых доказательств с использованием теоремы о рекурсии:## Теоремы Успенского-Райса ## Невычислимости Колмогоровской сложности ## Невычислимости Busy beaver ## аналога I теоремы Геделя о неполноте ## аналога II теоремы Геделя о неполноте ## теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)
# [[Busy beaver]]
