# Модульная контрольная II. Темы Доказательства теорем не будут включены в контрольную работу. В контрольной работе могут встретиться задания, которые предполагают понимание сути теорем. Во время контрольной **использование** шпаргалок, конспектов, учебников, слайдов, решений от третьих лиц (список неполный и будет трактоваться не в пользу студента) **не поощрается**. ## Вычислимые функции * Понятие вычислимой функции * Разрешимые множества * Перечислимые множества * Теорема поста * Понятие универсальной функции * Существование универсальной фукнции * Существование перечислимого неразрешимого множества * Определение примитивно-рекурсивной функции * Базисные функции * Композиция * Примитивная рекурсия * Оператор минимизации ## Бестиповое λ-исчисление * Определение терма в λ-исчислении * Снятие и расстановки скобок в λ-терме * Определение свободных переменных λ-терме * Определение связанных переменных λ-терме * α-конверсия * β-редукция * Теорема о неподвижной точке. Комбинатор неподвижной точки * Представление булевых значений и операций в λ-исчислении: * True * False * Конструкция if-then-else * Общее представление нумералов в λ-исчислении * Нумералы Чёрча * Представление примитивно рекурсивных функций λ-исчислении ## Практические задания, выходящие за рамки перечисленных выше пунктов * Уметь определить, является ли заданная функция примитивно рекурсивной или нет * По приведенной в задании контрольной фомуле уметь выполнить * Операции над булевыми значениями * Арифметические операции над нумералами **GLHF**