Qual é o sentido de chamar -calculus uma álgebra?

Qual é a diferença de chamar -calculus uma álgebra em vez de um cálculo? Faço essa pergunta porque li em algum lugar a linha " -calculus não é um cálculo, mas uma álgebra" (iirc, atribuído a Dana Scott). Qual é o ponto? Obrigado.$\lambda$$\lambda$

Um cálculo é um sistema de computação baseado na manipulação de expressões simbólicas. Uma álgebra é um sistema de expressões e relações simbólicas entre elas [*]. Ou seja, um cálculo é um sistema para descobrir respostas e uma álgebra é uma maneira de expressar as relações entre termos.

O -calculus é um cálculo ou uma álgebra, dependendo se você deseja pensar nas regras e como regras de redução orientadas ou equações não orientadas. Se você pensa nas regras como orientadas, fixou uma ordem de avaliação, e as regras informam como aceitar um termo e produzir uma forma normal. Se você acha que as regras não são orientadas, elas fornecem a relação de igualdade nos termos .β η $\lambda$$\beta$$\eta$$\lambda$

[*] Há também uma definição categórica de álgebra, que é uma definição formal um pouco mais restritiva do que a idéia informal. Em termos gerais, a diferença é que a definição formal de álgebra abrange apenas os sistemas sem ligação variável. Assim, os combinadores de SKI formam uma álgebra, mas o -calculus não.$\lambda$

Tradicionalmente, uma álgebra é um conjunto portador com operações que satisfazem algumas equações (pense em "grupo"). Existem muitas maneiras pelas quais a noção pode ser generalizada:

• álgebras multi-classificadas têm vários conjuntos de transportadoras. Um exemplo seria um módulo sobre um anel , onde queremos considerar a coisa toda como uma única álgebra. Outro exemplo, bastante tolo, é um gráfico direcionado, que possui dois conjuntos de portadores, de arestas e de vértices, e duas operações, fonte e alvo , que não satisfazem equações.R E V s : E → V E → $M$$R$$E$$V$$s : E \to V$$E \to V$

• axiomas mais gerais que não são apenas equações podem ser permitidos. Por exemplo, os axiomas de um campo são todas equações, exceto . Outro exemplo é algo como um domínio integral.$x \neq 0 \implies x \cdot x^{-1} = 1$

• operações mais gerais podem ser permitidas, em particular de aridade infinita, ou operações de ordem superior que assumem funções como argumentos. Um exemplo de operação infinita é o nas álgebras de ponto médio de Martin Escardo e Alex Simpson. Se você for longe nessa direção, chegará às mônadas.$M$

Nesse sentido, o -calculus não digitado é uma álgebra porque é especificado em termos de um conjunto de portadoras com algumas operações (de ordem superior) que satisfazem algumas equações ( e ).β $\lambda$$\beta$$\eta$

Existe uma definição bastante precisa do que é uma álgebra na teoria das categorias: veja este artigo, por exemplo. Demorou alguns anos para entender como uma estrutura com variáveis ​​ligadas poderia ser entendida no mesmo contexto que o termo estrutura de álgebra comumente usada em matemática e ciência da computação, e verifica-se que o conceito categórico de álgebras F é capaz de unificar o dois. Não tenho certeza sobre os aspectos históricos da solução, mas uma abordagem possível são as álgebras de presheaf introduzidas por Fiore, Plotkin e Turi (disponíveis aqui ), que resolveram a questão e estimularam abordagens diferentes, mas semelhantes, veja Hirshowitz et al. e sua aluna de doutorado Julianna Zsido .

Ainda há pesquisas a serem feitas sobre como usar os conceitos categóricos para refatorar e aprofundar nossa compreensão de estruturas com variáveis ​​ligadas, na esperança de eliminar o "cruft" sintático, que geralmente compreende os capítulos mais chatos de teses sobre -calculi e estruturas relacionadas.$\lambda$

Embora seja verdade que a noção de "cálculo" é menos bem definida do que a noção de "álgebra", geralmente "cálculo" geralmente implica um processo de cálculo, enquanto as álgebras têm padrões de construção com teorias equacionais.
Você poderia dizer que há mais um sentimento de que as álgebras "já existem" como estruturas e estamos apenas descobrindo verdades sobre elas, em vez de usar algum método para produzir novas respostas que não existiam antes.

Se você pensar sobre o que Scott estava tentando realizar com os domínios de Scott, sua afirmação faz sentido: ele estava tentando encontrar estruturas matemáticas e algébricas predefinidas que serviriam como uma semântica fixa para LC. Ele queria acabar com a sensação de que o significado de um termo era o que acontecesse como resultado de um processo específico.

Você pode estar interessado em uma resposta anterior sobre uma pergunta relacionada: O que constitui semântica denotacional?

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

Se Scott alguma vez chamou o cálculo lambda de "álgebra" (o que eu duvido), ele estaria fazendo uma observação bastante sutil, a saber, que você pode pensar no cálculo lambda como tendo um significado a priori .

Ainda assim, ele teria dificuldade em convencer qualquer algebraista de sua afirmação, porque ele não possui equações no cálculo lambda, ele possui equivalências (isto é, no nível meta). "Álgebra combinatória", por outro lado, é perfeitamente normal.

Não existe cálculo , mas existe um objeto matemático bem definido chamado álgebra , embora a palavra tenha muitos usos . No entanto, meu palpite é que o nome foi dado no sentido de

(...) o estudo abstrato de sistemas numéricos e operações dentro deles.

$\lambda$