Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем для формализации и анализа понятия вычислимости.
В математике и информатике подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.
Комбина́торная ло́гика — направление математической логики, занимающееся фундаментальными понятиями и методами формальных логических систем или исчислений. В дискретной математике комбинаторная логика тесно связана с лямбда-исчислением, так как описывает вычислительные процессы.
Градиентный спуск, метод градиентного спуска — численный метод нахождения локального минимума или максимума функции с помощью движения вдоль градиента, один из основных численных методов современной оптимизации.
Декартово замкнутая категория — категория, допускающая каррирование, то есть содержащая для каждого класса морфизмов 
некоторый объект 
, представляющий его. Декартово замкнутые категории занимают в некотором смысле промежуточное положение между абстрактными категориями и множествами, так как позволяют корректно оперировать с функциями, но не позволяют, к примеру, оперировать с подобъектами.
Типизированное лямбда-исчисление — это версия лямбда-исчисления, в которой лямбда-термам приписываются специальные синтаксические метки, называемые типами. Допустимы различные наборы правил конструирования и приписывания таких меток, они порождают различные системы типизации.
Каррирование — преобразование функции от многих аргументов в набор вложенных функций, каждая из которых является функцией от одного аргумента. Возможность такого преобразования впервые отмечена в трудах Готтлоба Фреге, систематически изучена Моисеем Шейнфинкелем в 1920-е годы, а наименование своё получила по имени Хаскелла Карри — разработчика комбинаторной логики, в которой сведение к функциям одного аргумента носит основополагающий характер.
Coq — интерактивное программное средство доказательства теорем, использующее собственный язык функционального программирования (Gallina) с зависимыми типами. Позволяет записывать математические теоремы и их доказательства, удобно модифицировать их, проверяет их на правильность. Пользователь интерактивно создаёт доказательство сверху вниз, начиная с цели. Coq может автоматически находить доказательства в некоторых ограниченных теориях с помощью так называемых тактик. Coq применяется для верификации программ.
Ля́мбда-куб (λ-куб) — наглядная классификация восьми типизированных лямбда-исчислений с явным приписыванием типов. Куб организован в соответствии с возможными зависимостями между типами и термами этого исчисления и формирует естественную структуру для исчисления конструкций. Идею λ-куба предложил в 1991 году нидерландский логик и математик Хенк Барендрегт. Дальнейшие обобщения лямбда-куба можно получить, рассматривая чистую систему типов.
Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.
Непрерывность по Скотту — свойство функций над частично упорядоченными множествами, выражающееся в сохранении точной верхней грани относительно отношения частичного порядка.
Соответствие Карри — Ховарда — наблюдаемая структурная эквивалентность между математическими доказательствами и программами, которая может быть формализована в виде изоморфизма между логическими системами и типизированными исчислениями.
Просто типизированное лямбда-исчисление — система типизированного лямбда-исчисления, в которой лямбда-абстракции приписывается специальный «стрелочный» тип. Эта система была предложена Алонзо Чёрчем в 1940 году. Для близкого к лямбда-исчислению формализма комбинаторной логики похожая система рассматривалась Хаскеллом Карри в 1934 году.
Система F — система типизированного лямбда-исчисления, отличающаяся от просто типизированной системы наличием механизма универсальной квантификации над типами. Эту систему разработал в 1972 году Жан-Ив Жирар в контексте теории доказательств в логике. Независимо от него подобную систему предложил в 1974 году Джон Рейнольдс. Система F позволяет формализовать концепцию параметрического полиморфизма в языках программирования и служит теоретической основой для таких языков программирования как Haskell и ML.
Двойственность, или принцип двойственности, — принцип, по которому задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу. Решение двойственной задачи даёт нижнюю границу прямой задачи. Однако, в общем случае, значения целевых функций оптимальных решений прямой и двойственной задач не обязательно совпадают. Разница этих значений, если она наблюдается, называется разрывом двойственности. Для задач выпуклого программирования разрыв двойственности равен нулю при выполнении условий регулярности ограничений.
Теория комбинаторных схем — это часть комбинаторики, рассматривающая существование, построение и свойства семейств конечных множеств, структура которых удовлетворяет обобщённым концепциям равновесия и/или симметрии. Эти концепции не определены точно, так что объекты широкого диапазона могут пониматься как комбинаторные схемы. Так, в одном случае комбинаторные схемы могут представлять собой пересечения множеств чисел, как в блок-схемах, а в другом случае могут отражать расположение элементов в судоку.
Коррадо Бём — итальянский математик, специалист в области информатики и математической логики, внёсший решающий вклад в теоретическое обоснование парадигмы структурного программирования и получивший важные результаты в λ-исчислении, комбинаторной логике, семантике языков программирования; один из ранних исследователей теории языков программирования. Профессор римского университета «Сапиенца», сооснователь факультетов информатики Туринского университета и «Сапиенцы».
Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени, математическая оптимизация в общем случае NP-трудна.
В математике кодирование Чёрча означает представление данных и операторов в процедуре лямбда-исчисления. Необходимость процедуры вызвана тем, что в чистом лямбда-исчислении среди термов присутствуют только переменные и отсутствуют константы. Для того, чтобы получить объекты, ведущие себя таким же образом как и числа, применяется кодирование Чёрча. Сама процедура названа в честь Алонзо Чёрча, разработавшего лямбда-исчисление и впервые применившего этот метод кодирования данных. По аналогии с числами, кодирование Чёрча может быть применено и для представления объектов других типов, ведущих себя как константы.
