# Scala Course 2022 Autumn. Зачет

## Структура билета
Весь курс разбит на четыре главные темы:
* машины Тьюринга;
* вычислимые функции;
* бестиповое λ-исчисление;
* Scala.

Каждый билет будет состоять из следующих частей:
* Часть А
* первый вопрос: комплексный вопрос или вопрос на доказательство;
* Часть B
* второй вопрос: вопрос на описание, определение или формулировку без доказательства;
* третий вопрос: вопрос на описание, определение или формулировку без доказательства;
* Часть C
* практическое задание;
* решение задачи на Scala.

## Выбор билета
1. Я генерирую случайное число от 1 до 13. Результатом будет номер вопроса из части A.
2. Случайным образом выбираются 2 темы, из списка тем, за исключением той темы, которая вошла в первый вопрос. По каждой из двух тем проводится процедура, описанная выше, т.о. выбираются два вопроса из части B.
3. Я даю одно практическое задание или на машину Тьюринга, или на λ-исчисление по своему усмотрению.
4. Я даю задачу для решения на Scala.

### Вычислимые функции
1. Перечислимые множества, эквивалентные определения перечислимых множеств. Доказательство эквивалентности двух определений на выбор.
2. Теорема об объединении и пересечении перечислимых множеств. Доказательство.
3. Теорема Поста. Доказательство.
4. Понятие универсальной функции. Теорема о существовании универсальной функции. Доказательство.
5. Теорема о (не)существовании всюду определенной универсальной функции. Доказательство.
6. Теорема о существовании вычислимой функции, от которой любая другая функция не может всюду отличаться. Доказательство.
7. Теорема о существовании вычислимой функции, не имеющей всюду определенного определенного вычислимого продолжения. Доказательство.

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

## Вопросы к части B
### Машина Тьюринга
1. Понятие вычислимости по Тьюрингу.
2. Задание одноленточной машины Тьюринга.
3. Конфигурация одноленточной машины Тьюринга.
4. Протокол одноленточной машины Тьюринга.
5. Детерминизм машины Тьюринга.
6. Задание многоленточной машины Тьюринга.
7. Конфигурация многоленточной машины Тьюринга.
8. Протокол многоленточной машины Тьюринга.
9. Связь одноленточной и многоленточной машин Тьюринга.

### Вычислимые функции
1. Понятие вычислимой функции.
2. Разрешимые множества.
3. Перечислимые множества.
4. Теорема Поста.
5. Понятие универсальной функции.
6. Перечислимое неразрешимое множество. Проблема останова.

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

### Scala
1. Понятие ссылочной прозрачности. Чистая функция. Примеры и контрпримеры.
2. Функции в Scala, связь функций и def. Рекурсивные функции.
3. Хвостовая рекурсия.
4. Функции высших порядков.

**GLHF**