3622
правки
Изменения
→Вычислительные формализмы
=== Вычислительные формализмы ===
<ol>
<li value="12">'''!!!''' [[Машина Тьюринга]] (7) </li>
# Англоязычные термины
# Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
# Заменить ссылки на источники информации
# Добавить категории
<li> '''fixed''' [[Лямбда-исчисление]]</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> '''!!!''' [[Примитивно рекурсивные функции]] (6) </li>
# названия функций надо в \mathrm
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
<li> '''взяли''' [[Частично рекурсивные функции]] (5) </li>
# См. замечания в обсуждениях
# англоязычные термины
# Оформить правильно источники информации
# Добавить категории
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]](0.5) </li>
# Интервики
# Разбить доказательство на абзацы для читабельности
# Добавить категории
# Правильно оформить источники информации
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] (0.5) </li>
# Оформить правильно источники информации
# Добавить категории
<li> [[Линейный клеточный автомат, эквивалентность МТ]] (0.5) </li>
# Англоязычные термины правильно оформить
# Переменные взять в Tex
# Добавить категории
# Оформить правильно источники информации
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] (1) </li>
# внутренние ссылки
# категории
# Добавить см. также и источники информации
<li> [[Линейный ограниченный автомат]]</li>
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
</ol>
