Quais funções as expressões de cálculo combinador podem calcular?

13

Uma expressão combinadora (digamos na base SK) pode ser pensada como uma função que mapeia expressões de cálculo combinador para expressões de cálculo combinador. Ou seja, pode-se pensar em uma expressão X como uma função X:eueu , onde eu é o conjunto de todas as expressões combinadoras sintaticamente válidas na base SK. Esse mapeamento é realizado aplicando a entrada à expressão e depois reduzindo para a forma normal para obter a saída.

Como a base SK é Turing completa, pode-se ingenuamente pensar que existe uma uma SK expressão que implementa qualquer função computável de L a L . No entanto, isso claramente não é o caso, pois o resultado da redução sempre estará na forma normal. Isso significa que não há como uma expressão ter uma saída que não esteja na forma normal.Xeueu

Então, em vez disso, eu poderia pensar nas expressões de cálculo SK como mapeando para L , onde L é o conjunto de expressões SK na forma normal. É o caso de que, para qualquer mapa computável f : L L , existe uma expressão SK X que implementa esse mapa? Ou existem outras restrições no conjunto de funções que podem ser calculadas por expressões de cálculo combinador dessa maneira?eueueuf:eueuX

Nathaniel
fonte

Respostas:

6

Para fazer a bola rolar, e na esperança de outras pessoas dar respostas mais profundas e detalhadas sobre a estrutura das funções definíveis L L , deixe-me citar o Corolário 20.3.3 do The Lambda Calculus de Barendregts , sua sintaxe e Semântica (também conhecida como "a Bíblia").λeueu

Corolário 20.3.3: A função , definido por δ ( M , N ) = { T r u e  se  M = p r | N F um l s e  de outro modo não é definível no untyped λ - cálculo, ou seja, não existe um termo D tal que D M N = β η δ ( M , N )δ:eu2eu

δ(M,N)={Trvocêe E se M=βηNFumaeuse de outra forma
λD
D M N=βηδ(M,N)
para todos os .M,Neu

A prova envolve considerações nas árvores de Böhm, que fornecem uma caracterização bastante forte das possíveis "ações" de termos arbitrários de lambda em formas normais. Em particular, para qualquer termo fechado não constante , on pode encontrar n N e P 1 , , P n de modo que F x P 1P n = β η x Q 1Q kFnNP1,...,Pn

F x P1...Pn=βηx Q1...Qk

kQ1,...,QkDδD

cody
fonte