# Вопросы к зачету (заочная форма обучения)

1. Задание одноленточной машины Тьюринга. Конфигурация одноленточной машины Тьюринга. Протокол одноленточной машины Тьюринга. Детерминизм машины Тьюринга. Вычислимость по Тьюрингу.
2. Понятие вычислимой функции и вычислимости (по Геделю).
3. Определение терма в λ-исчислении. Снятие и расстановки скобок в λ-терме.
4. Определение свободных переменных λ-терме. Определение связанных переменных λ-терме. α-конверсия. Правила замены.
5. β-редукция. Правила подстановки.
6. Теорема о неподвижной точке. Комбинатор неподвижной точки. Доказательство.
7. Представление булевых значений и операций в λ-исчислении: True, False, конструкция if-then-else.
8. Общее представление нумералов в λ-исчислении, нумералы Чёрча, операция succ.
9. Нормальная форма, сильная и слабая нормализуемость λ-терма. Теорема Чёрча-Россера (без доказательства). Следствие о единственности нормальной формы (с доказательством).
10. Понятие ссылочной прозрачности. Чистая функция. Примеры и контрпримеры (из языков программирования).
11. Рекурсивные функции, хвостовая рекурсия (примеры из языков программирования).