=== Вычислительные формализмы ===
# <ol><li value="12">'''!!!''' [[Машина Тьюринга]]</li>## Англоязычные термины## Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)## Выделить машину Тьюринга жирным в определении## Алгоритмы примеров красиво оформить## Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)## Добавить в многоленточной, что эмулируется многодорожечной## Рассказать весёлую историю про тезис Чёрча-Тьюринга## Заменить ссылки на источники информации## Добавить категории# <li> '''!!!''' [[Лямбда-исчисление]] ''(можно получить 10 баллов суммарно)''</li>## Англоязычные термины## Заменить "в разработке" на "nohate"## Написать грамматику лямбд адекватно## "Аппликация забирает себе всё," - ошибка - абстракция забирает## Провести аналогию между связанными переменными и локальными переменными## "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?## Написать, что alpha-конверсия -- отношение эквивалентности## beta-редукция не олицетворяет. Написать определение формально## Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней## Провести аналогию между нумералами Чёрча и нумерацией Гёделя## Убрать маркированный список из чисел, лучше просто отступ оставить## "<<числу>>" {{---}} получше оформить## Все константы и переменные взяь в Tex## Добавить примеры выполнения операций сложения, умножения и вычитания## "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается## Добавить в неподвижной точке про Y-комбинатор## Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном## Оформить правильно источники информации, см. также## Добавить категории# <li> '''!!!''' [[Примитивно рекурсивные функции]]</li>## названия функций надо в \mathrm## Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]# <li> '''!!!''' [[Частично рекурсивные функции]]</li>## См. замечания в обсуждениях## англоязычные термины## Дефис заменить на тире## "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом## Заменить знаки неравенств ## "неразрешимость проврк," {{---}} опечатки## Оформить правильно источники информации## Добавить категории# <li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li>## Интервики## Разбить доказательство на абзацы для читабельности## Добавить категории## Правильно оформить источники информации# <li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]</li>## Оформить правильно источники информации## Добавить категории# <li> [[Линейный клеточный автомат, эквивалентность МТ]]</li>## Англоязычные термины правильно оформить## Переменные взять в Tex## Добавить категории## Оформить правильно источники информации# <li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]</li>## внутренние ссылки## категории## Добавить см. также и источники информации</ol>
=== Примеры неразрешимых задач ===
# <ol><li value="20"> '''!!!''' [[m-сводимость]]</li>## Англоязычные термины правильно оформить## Добавить примеры m-сведения задач## Заменить знаки неравенств## Добавить категории## Ссылку на ПСП оформить правильно## Переменные и константы взять в Tex# <li> '''!!!''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]</li>## Англоязычные термины правильно оформить## Заменить дефисы на тире## Заменить знаки неравенств## Все переменные и константы взять в Tex## Добавить примеров решения задач ПСП## Отфомартировать псевдокод## Добавить больше подзаголовков нижнего уровня## Больше интервики## Заменить источники на источники информации## Добавить категории, см. также# <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]</li>## Источники информации## Добавить см. также# <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]</li>## Добавить см. также# <li> '''!!!''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]</li>## Оформить правильно англоязычные термины## Написать более подробное и понятное доказательство## Заменить ссылки на источники информации## Добавить категории## Добавить см. также# <li> '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]</li>## Англоязычные термины оформить правильно## Заменить дефисы на тире## Заменить прим. на более адекватный аналог## Заменить источники на источники информации## Добавить информацию по последнему замечанию из обсуждений## Добавить см. также# <li> [[Неразрешимость исчисления предикатов первого порядка]]</li>## Добавить см. также## Заменить ссылки на источники информации# <li> '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]</li>## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.# <li> '''!!!''' [[Теорема Райса-Шапиро]]</li>## Англоязычные термины## Отформатировать псевдокоды## Дать более формальное и понятное определение образца## Разбить доказательство на две части, чтобы это было видно## Написать строгую формулировку теоремы## "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие## Лучше явно написать разрешитель для K## "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней## Добавить категории, см. также## Заменить литературу на источники информации</ol>
