Какой смысл называть

Какая разница в том, чтобы называть калькуляцию алгеброй вместо исчисления? Я поднимаю этот вопрос, потому что где-то прочел строку « λ- калькуляция - это не исчисление, а алгебра» (iirc, приписывается Дане Скотт). Какой смысл? Спасибо.$\lambda$$\lambda$

Исчисление - это система вычислений, основанная на манипулировании символическими выражениями. Алгебра - это система символических выражений и отношений между ними [*]. То есть исчисление - это система определения ответов, а алгебра - это способ выражения отношений между терминами.

-исчисления либо исчисление или алгебра, в зависимости от того, хотите ли вы думать о р и п правил как ориентированных правил редукции или неориентированных уравнений. Если вы думаете, что правила ориентированы, то вы установили порядок оценки, и правила говорят вам, как взять термин и создать нормальную форму. Если вы думаете о правилах как о неориентированных, то они дают вам соотношение равенства по λ- терминам.$\lambda$$\beta$$\eta$$\lambda$

[*] Существует также категорическое определение алгебры, которое является формальным определением, несколько более ограничительным, чем неформальная идея. Грубо говоря, разница в том, что формальное определение алгебры охватывает только те системы, которые не связаны с переменным связыванием. Таким образом, комбинаторы SKI образуют алгебру, а вычисление - нет.$\lambda$

Традиционно алгебра - это набор носителей с операциями, которые удовлетворяют некоторым уравнениям (например, «группа»). Существует много способов обобщения этого понятия:

• многосортные алгебры имеют несколько наборов носителей. Примером может служить модуль над кольцом R , где мы хотим рассматривать все это как одну алгебру. Другой, довольно глупый пример - это ориентированный граф, который имеет два набора носителей, E ребер и V вершин, и две операции, источник s : E → V и цель E → V , не удовлетворяющие никаким уравнениям.$M$$R$$E$$V$$s : E \to V$$E \to V$

• могут быть разрешены более общие аксиомы, которые не являются просто уравнениями. Например, аксиомы для поля - это все уравнения, кроме . Другой пример - это что-то вроде интегральной области.$x \neq 0 \implies x \cdot x^{-1} = 1$

• могут быть разрешены более общие операции , в частности операции бесконечной арности или операции более высокого порядка, которые принимают функции в качестве аргументов. Примером бесконечной операции является в алгебрах средних точек Мартина Эскардо и Алекса Симпсона. Если вы идете далеко в этом направлении, вы получите монады.$M$

В этом смысле нетипизированный калькуляция является алгеброй, поскольку она задается в терминах множества носителей с некоторыми операциями (высшего порядка), удовлетворяющими некоторым уравнениям ( β и η ).$\lambda$$\beta$$\eta$

Существует довольно точное определение того, что алгебра в теории категорий: см. Эту статью, например. Потребовалось несколько лет, чтобы понять, как структуру со связанными переменными можно понимать в том же контексте, что и термин структура алгебры, обычно используемый в математике и информатике, и оказывается, что категориальная концепция F-алгебр способна объединить два. Я не уверен насчет исторических аспектов решения, но одним из возможных подходов является то, что алгебры с предварительными пучками, введенные Fiore, Plotkin и Turi (доступны здесь ), решили вопрос и стимулировали разные, но схожие подходы, см., Например, Hirshowitz et al. и его аспирантка Джулианна Зсидо .

$\lambda$

Хотя верно и то, что понятие «исчисление» менее четко определено, чем понятие «алгебра», в целом «исчисление» обычно подразумевает процесс вычисления, в то время как алгебры имеют схемы построения с эквациональными теориями.
Вы могли бы сказать, что существует ощущение, что алгебры «уже существуют» как структуры, и мы просто раскрываем правду о них, а не используем какой-то метод для получения новых ответов, которых раньше не было.

Если вы думаете о том, что Скотт пытался достичь с помощью доменов Скотта, его утверждение имеет смысл: он пытался найти предопределенные математические и алгебраические структуры, которые служили бы фиксированной семантикой для LC. Он хотел избавиться от ощущения, что значение термина - это то, что произошло в конкретном процессе.

Возможно, вас заинтересует предыдущий ответ по связанному вопросу: что представляет собой денотационная семантика?

$\beta$$\eta$$M$$N$

Если бы Скотт когда-либо называл лямбда-исчисление «алгеброй» (в чем я, скорее, сомневаюсь), то он сделал бы довольно тонкое замечание, а именно, что вы можете думать о лямбда-исчислении как имеющем априорное значение.

Тем не менее ему было бы трудно убедить любого алгебраиста в своем утверждении, потому что у него нет уравнений в лямбда-исчислении, у него есть эквивалентности (то есть на мета-уровне). «Комбинаторная алгебра», с другой стороны, совершенно нормальная.

Не существует такого понятия, как исчисление , но существует четко определенный математический объект, называемый алгеброй , хотя это слово имеет множество применений . Тем не менее, я предполагаю, что название было дано в смысле

(...) абстрактное исследование систем счисления и операций в них.

$\lambda$