---
# System prepended metadata

title: Модульная контрольная II. Темы

---

# Модульная контрольная II. Темы

Доказательства теорем не будут включены в контрольную работу. 

В контрольной работе могут встретиться задания, которые предполагают понимание сути теорем.

Во время контрольной **использование** шпаргалок, конспектов, учебников, слайдов, решений от третьих лиц (список неполный и будет трактоваться не в пользу студента) **не поощрается**.

## Вычислимые функции
* Понятие вычислимой функции
* Разрешимые множества
* Перечислимые множества
* Теорема поста
* Понятие универсальной функции
* Существование универсальной фукнции
* Существование перечислимого неразрешимого множества
* Определение примитивно-рекурсивной функции
  * Базисные функции
  * Композиция
  * Примитивная рекурсия
* Оператор минимизации

## Бестиповое λ-исчисление
* Определение терма в λ-исчислении
* Снятие и расстановки скобок в λ-терме
* Определение свободных переменных λ-терме
* Определение связанных переменных λ-терме
* α-конверсия
* β-редукция
* Теорема о неподвижной точке. Комбинатор неподвижной точки
* Представление булевых значений и операций в λ-исчислении:
  * True
  * False
  * Конструкция if-then-else
* Общее представление нумералов в λ-исчислении
* Нумералы Чёрча
* Представление примитивно рекурсивных функций λ-исчислении

## Практические задания, выходящие за рамки перечисленных выше пунктов
* Уметь определить, является ли заданная функция примитивно рекурсивной или нет
* По приведенной в задании контрольной фомуле уметь выполнить 
  * Операции над булевыми значениями
  * Арифметические операции над нумералами

**GLHF**