Este artigo sugere que existem combinadores (representando cálculos simbólicos) que não podem ser representados pelo cálculo Lambda (se eu entendi as coisas corretamente):
Há várias coisas que se pode querer fazer na prática e que não podem ser expressas diretamente no cálculo lambda.
O cálculo do SF é um exemplo. Seu poder expressivo não é novidade; a parte interessante do artigo (não mostrada nos slides) é a teoria das categorias por trás dele. O cálculo do SF é análogo a uma implementação lisp, na qual você permite que as funções inspecionem a representação de seus argumentos - para que você possa escrever coisas como(print (lambda (x) (+ x 2))) ⟹ "(lambda (x) (+ x 2))".
Outro exemplo importante é o paralelo de Plotkin ou . Intuitivamente, há um resultado geral que afirma que o cálculo lambda é seqüencial: uma função que usa dois argumentos deve escolher um para avaliar primeiro. É impossível escrever um termo lambda de ormodo que ( or⊤ ⊥) ⟹ ⊤, (or ⊥ ⊤) ⟹ or⊥ e ⊥ ⊥ ⟹ ⊥ (onde ⊥ é um termo que não termina e ⊤ é um termo que termina). Isso é conhecido como "paralelo ou" porque uma implementação paralela pode fazer uma etapa de cada redução e parar sempre que um dos argumentos termina.
Outra coisa que você não pode fazer no cálculo lambda é entrada / saída. Você precisaria adicionar primitivos extras para isso.
Obviamente, todos esses exemplos podem ser representados no cálculo lambda adicionando um nível de indireção, representando essencialmente termos lambda como dados. Mas o modelo se torna menos interessante - você perde a relação entre funções na linguagem modelada e abstrações lambda.
A resposta para sua pergunta depende de como você define "cálculos" e "representados". O tópico no LTU que o sclv mencionou , por outro lado, consiste principalmente de pessoas conversando entre si devido a definições desalinhadas de vários termos.
A distinção certamente não é de poder computacional - todo sistema em consideração é equivalente a Turing. O problema é que a mera equivalência de Turing não diz realmente nada sobre a estrutura ou a semântica de uma expressão. Nesse caso, em modelos extremamente minimalistas de computação que exigem codificações complexas ou estados iniciais não triviais, pode até não estar claro se um sistema é capaz de computação universal ou se uma ilusão de universalidade está sendo criada pela interpretação de alguém do sistema. . Por exemplo, veja esta discussão na lista de discussão sobre uma máquina de Turing de 2 estados e 3 símbolos, particularmente as preocupações levantadas por Vaughan Pratt.
De qualquer forma, a distinção feita é entre algo como:
A equivalência de Turing implica apenas que um sistema atenda ao terceiro critério para qualquer função computável, enquanto esse é o primeiro critério com o qual nos preocupamos, seja em um sistema formal de lógica ou em uma linguagem de programação (na medida em que realmente diferem).
Essa é uma descrição muito informal, mas a idéia essencial pode ser definida com mais precisão. No segmento LtU mencionado acima, podem ser encontradas algumas referências ao trabalho existente em linhas semelhantes.
Tanto a lógica combinatória de Schönfinkel quanto o λ-cálculo de Church foram inicialmente concebidos como abstrações destiladas do raciocínio lógico e, como tal, sua estrutura mapeia muito bem o raciocínio lógico e vice-versa. Eles também carregam uma suposição de extensionalidade , como descrito pela regra de redução de eta: λx. f xonde xnão ocorre f, é equivalente a apenas um f.
Na prática, uma noção muito estrita de extensionalidade pode ser muito limitadora, enquanto a intensionalidade irrestrita torna difícil ou impossível o raciocínio local sobre subexpressões.
O cálculo SF é um cálculo combinador modificado que fornece, como uma operação primitiva, uma forma limitada de análise intensional: a capacidade de desconstruir expressões parcialmente aplicadas, mas não valores primitivos ou expressões não normalizadas. Isso acontece de mapear muito bem idéias como a correspondência de padrões, encontrada nas linguagens de programação do estilo ML ou macros, como encontradas no Lisps, mas não pode ser descrita no cálculo SK ou λ sem, efetivamente, implementar um intérprete para avaliar termos "intensionais".
Portanto, em resumo: o cálculo SF não pode ser representado diretamente no cálculo λ no sentido de que a melhor representação possível envolve a implementação de um intérprete de cálculo SF, e a razão disso é uma diferença semântica fundamental: as expressões têm estrutura, ou eles são definidos apenas por seu comportamento externo?
O cálculo de SF de Barry Jay é capaz de examinar a estrutura dos termos aos quais é aplicada, o que não é funcional. O cálculo lambda e a lógica combinatória tradicional são puramente funcionais e, portanto, não podem fazer isso.
Existem muitas extensões do cálculo lambda que fazem coisas que violam a pureza, a maioria das quais requer a correção da estratégia de reescrita em algum grau, como adicionar estado, controles (por exemplo, via continuações) ou variáveis lógicas.
fonte