3622
правки
Изменения
→Разрешимые и перечислимые языки
== 3. Теория вычислимости (проверяется) ==
=== Разрешимые и перечислимые языки ===
# '''fixed''' [[Разрешимые (рекурсивные) языки]]## Оформить правильно англоязычные термины## Отформатировать псевдокод## Перенести сюда определение вычислимой функции## Добавить определение разрешимого языка в терминах вычислимой функции## Заменить источники на источники информации## Обернуть if в доказательстве неразрешимого языка в \mathrm## Ещё примеров разрешимых языков (желательно не очень тривиальных)# '''!!!''' [[Перечислимые языки]](6)
## Оформить правильно англоязычные термины
## Поправить чуть определение полуразрешимого языка
## Заменить источники на источники информации
## Добавить примеры перечислимых, коперечеслимых языков и неперечислимых языков
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]](1)
## Чуть-чуть код форматнуть
## Заменить литературу на источники информации
# [[Вычислимые функции]](0.5)
## Заменить источники на источники информации
## Определения вычислимой функции перенести в конспект Разрешимых языков## Переименовать конспект и чуть-чуть реструктуризоватьАнглоязычные термины# [[Вычислимые числа]](1)
## Правильно оформить англоязычные термины
## Пояснить a(eps) в определении
## Ссылки заменить на источники информации
## Увеличить дроби
# [[Универсальная функция]] (1)
## Англоязычные термины правильно оформить
## Оформить правильно источники информации
## Заменить дефисы на тире
# '''fixed''' # Пояснить нотацию про U(n, x) и U_n(x)## Заголовки внутри конспекта поправить# [[Свойства перечислимых языков. Теорема Успенского-Райса]](1)## англоязычные термины## классы языков в mathrm## заголовки верхнего уровня в ==Почему языком L_g(i, а не =x) будет X? Как i связано с X? ## категорию проставитьИ вообще доказательство можно сделать чуть менее мутным :)## Добавить источники информации## Заменить в множестве | на \mid## Отформатировать псевдокод# '''fixed''' [[Неотделимые множества]]## английские источиники и термины ## нормально оформить уже существующий источник ## написать, зачем оно может пригодиться## Добавить категории## Интервики# '''!!!''' [[Иммунные и простые множества]](7)
## английские источиники и термины
## ссылки на вики
## Подробней расписать доказательства
## Ссылки на леммы внутри конспекта
# '''!!!''' [[Теорема о рекурсии]](8)
## дать ссылки на английские источники и термины
## Неформальное пояснение к теореме
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
# [[Квайны]]# [[Busy beaver]](1)
## Правильно оформить англоязычные термины
## Отформатировать псевдокод
## Нормально оформить см. также, источники информации и вывод из теоремы
# [[Колмогоровская сложность]]
=== Вычислительные формализмы ===
