Изменения

== '''в процессе проверки''' 3. Теория вычислимости ==

# '''!!!''' [[Машина Тьюринга]]# # Англоязычные термины## Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)## Выделить машину Тьюринга жирным в определении## Алгоритмы примеров красиво оформить## Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)## Добавить в многоленточной, что эмулируется многодорожечной## Рассказать весёлую историю про тезис Чёрча-Тьюринга## Заменить ссылки на источники информации## Добавить категории# '''!!!''' [[Лямбда-исчисление]]''(можно получить 10 баллов суммарно)''## Англоязычные термины## Заменить "в разработке" на "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-комбинатор## Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном## Оформить правильно источники информации, см. также## Добавить категории# '''!!!''' [[Примитивно рекурсивные функции]]## названия функций надо в \mathrm или \mathtt## привести пример использования теоремы о примитивной рекурсивностиПомёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]# '''!!!''' [[Частично рекурсивные функции]]## См. замечания в обсуждениях

## Дефис заменить на тире## "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом## Заменить знаки неравенств ## "неразрешимость проврк," {{---}} опечатки## Оформить правильно источники информации## Добавить категории# [[Стековые машины, эквивалентность двухстековой машины МТ]]## Интервики## Разбить доказательство на абзацы для читабельности## Добавить категории## Правильно оформить источники информации

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

## Добавить см. также# '''взяли!!!''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]## замечания в обсужденииОформить правильно англоязычные термины## Написать более подробное и понятное доказательство## Заменить ссылки на источники информации## Добавить категории## Добавить см. также# '''взяли!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]## замечения в обсужденииАнглоязычные термины оформить правильно## Заменить дефисы на тире## Заменить прим. на более адекватный аналог## Заменить источники на источники информации## Добавить информацию по последнему замечанию из обсуждений## Добавить см. также# '''взяли''' [[Неразрешимость исчисления предикатов первого порядка]]## написатьДобавить см. Это очень просто также## Заменить ссылки на самом деле, если немного помнить матлогикуисточники информации

# '''!!!''' [[Теорема Райса-Шапиро]]## Англоязычные термины## Отформатировать псевдокоды## Дать более формальное и понятное определение образца## Разбить доказательство на две части, чтобы это было видно## Написать строгую формулировку теоремы## "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие## Лучше явно написать разрешитель для K## "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней## Добавить категории, см. также## Заменить литературу на источники информации