Como os termos-

14

Eu estive pensando sobre estas perguntas:

Existe um cálculo lambda digitado que seja consistente e Turing completo?

/cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent

e já existem algumas questões difíceis de responder relacionadas na configuração sem tipo! Mais especificamente, estou curioso para saber se podemos recuperar a integridade de Turing da não terminação da seguinte maneira:

Pergunta: Dado um (puro) λ -termo t com nenhuma forma normal cabeça fraca, não existe sempre existir um elemento de combinação de ponto fixo Yt de tal forma que

Yt (λx.x)=t

Todas as igualdade são tomadas no módulo βη .

Na verdade, eu suspeito que esta versão da pergunta seja falsa , para que se possa relaxar a questão para combinadores em loop , em que um combinador em loop Y é definido como um termo tal que para cada f

Y f=f (Y f)
onde Y é novamente necessário que seja um combinador de loop. Isso é suficiente para definir funções recursivas como de costume, é claro.

De maneira mais geral, estou interessado em encontrar maneiras "naturais" de passar de um sem terminação tpara um combinador de loop, mesmo que a equação acima não seja satisfeita.

Eu também estou interessado em versões mais fracos da pergunta acima, por exemplo, t pode ser considerado como sendo uma aplicação tt1 t2...tn a cada tEu na forma normal (embora eu não tenho certeza de que realmente ajuda).


Até agora: a abordagem natural é aplicar t "pimenta" de f todo o processo, por exemplo

Ω: =(λx.x x)(λx.x x)

torna-se o habitual

YΩ: =λf.(λx.f (x x)) (λx.f (x x))

A idéia é reduzir a cabeça de t para um aplicativo lambda λx.t e substitua-o por λx.f t , mas o próximo passo não é claro (e eu sou cético quanto a isso poder levar a qualquer coisa).

Não tenho certeza eu entendo o suficiente sobre árvores Böhm para ver se eles têm alguma coisa a dizer, mas eu duvido muito, desde Ω Böhm árvore 's é simplesmente , que parece em nada com a pessoa certa para YΩ : uma árvore infinita de abstrações.


Edit : Um amigo meu observou que esta abordagem ingênua não funciona com o termo:

(λx.x x x)(λx.x x x)
A abordagem ingênua daria
(λx.f (x x x))(λx.f (x x x))
Mas este não é um combinador de pontos fixos! Isso pode ser corrigido substituindo a segunda aplicação de f por , mas então f eu não dá ao termo original. Não está claro se esse termo é um contra-exemplo para a pergunta original (e certamente não é um contra-exemplo para a mais geral).λyz.f yfEu
cody
fonte
Acredito que o requisito de que t não tenha a forma normal da cabeça deve ser reforçado para excluir também formas normais da cabeça fraca. Se t é capaz de produzir um lambda, então, como na posição da cabeça você sempre tem um combinador de ponto de fixação (começando com f = id), o lambda deve ser produzido por ele, isso não é possível.
Andrea Asperti 15/03/19
@AndreaAsperti você está certo, é claro. Vou alterar a pergunta.
Cody

Respostas:

7

Existem vários aspectos para essa pergunta muito legal, portanto estruturarei esta resposta de acordo.

1. A resposta para a pergunta em caixa é não . Os termo sugerido pelo seu amigo é realmente um contra-exemplo.Ω3=(λx.xxx)(λx.xxx)

Foi observado anteriormente nos comentários que se tem contra-exemplos como o "ogro" , até que a questão seja restrita a termos sem forma normal de cabeça fraca. Tais termos são conhecidos comotermos zero. Estes são termos que nunca se reduzem a um lambda, sob qualquer substituição.K=YK

Para qualquer combinador de ponto fixo (fpc) ,Y é o chamadotermomudo(AKA "root-active"): cada redução do mesmo reduz-se ainda mais a um redex.YEu

não é mudo; nem é Ω 3 - como é manifestado pela inspeção de seu conjunto de redutos, que é { Ω 3 ( λ x . x x x ) ( λ x . x x x ) kKΩ3 -

{Ω3(λx.xxx)(λx.xxx)kkN}

Em vez de apresentar um argumento preciso por que é mudo para todos os fpcs YYEuY (de fato, para qualquer combinador de loop) que pode ser trabalhoso, mas esperançosamente claro o suficiente - , tratarei a generalização óbvia de sua pergunta, restringindo também os termos mudos.--

Termos mudos são uma subclasse de termos zero que são uma subclasse de termos insolúveis. Juntas, essas são talvez as escolhas mais populares para o conceito de "sem sentido" ou "indefinido" no cálculo lambda, correspondendo às árvores triviais de Berarducci, Levy-Longo e B \ ohm, respectivamente. A estrutura de noções de termos sem sentido foi analisada em detalhes por Paula Severi e Fer-Jan de Vries. [1] Os termos mudos constituem o elemento inferior dessa treliça, ou seja, a noção mais restritiva de "indefinido".

2. Seja um termo mudo e Y seja um combinador de loop com a propriedade que YMY .YEu=M

Primeiro, argumentamos que, para uma variável nova , Y z se parece muito com o Y M que você descreveu, obtido por "aspersão zzYzYMz em torno de" alguns reduct de .M

Por Church-Rosser, e M têm um reduto comum, M . Faça uma redução padrão R : Y I ' s M ' . Todo subtermo de M corresponde a um subtermo único de Y I Y z [ z : = I ] sob esta redução. Para qualquer subtermo C [ N ] = M , fatores R como N 0 ] wYEuMMR:YEusMMYEuYz[z: =Eu]C[N]=MR, em que a perna do meio é uma redução de cabeça fraca (e etapa final é interna). Né "guardado" por umzse esta segunda etapa contrair algum redexIP, comIum descendente da substituição[z:=I].YEuC[N0 0]WhC[N1]EuC[N]NzEuPEu[z: =Eu]

Obviamente, tem que guardar alguns subtermos de M , caso contrário seria mudo também. Por outro lado, deve-se ter cuidado para não guardar os subtermos necessários para a não terminação, pois, caso contrário, não poderá desenvolver a árvore B \ "ohm infinita de um combinador em loop.YM

Assim, basta encontrar um termo mudo no qual todo subtermo, de cada redução, é necessário para a não normalização, no sentido de que colocar uma variável na frente desse subtermo produz um termo normalizador.

Considere , onde W = λ w . w eu w w . É como Ω , mas a cada iteração, verificamos que a ocorrência de W na posição do argumento não é "bloqueada" por uma variável head, alimentando-a com uma identidade. Colocar um z na frente de qualquer subtermo resultará em uma forma normal de forma z P 1P k , onde cada P i é I , W ou a " zΨ=WWW=λW.WEuWWΩWzzP1PkPEuEuWz borrão " deles. Então Ψ é um contra-exemplo para a questão generalizada.

TEOREMA. Não existe um combinador de loop tal que Y I =Y .YEu=Ψ

PROVA. O conjunto de todas as redutos de é { W W , W I W W , I I I I W W , I I I W W , I I W W , I W W } . Para ser conversível com Ψ , Y devo reduzir a um deles. O argumento é idêntico em todos os casos; para concreção, suponhamos que Y I I I W W .Ψ{WW,WIWW,IIIIWW,IIIWW,IIWW,IWW}ΨYEuYEuEuEuWW

Qualquer redução padrão pode ser tomada como Y I w P N 4 , P W Q N 3 , Q w N 1 N 2 , assim  Y I w N 1 N 2 N 3 N 4 N 1I , N 2I , N 3YEusEuEuWW

YEuWPN4,PWQN3,QWN1N2,portanto YEuWN1N2N3N4N1Eu,N2Eu,N3W,N4W

Vamos nos referir à redução como R 0 , e as reduções a partir de N i como R iYEuWN1N2N3N4R0 0NEuREu .

Estas reduções podem ser levantado através da substituição para produzir R z 0 : Y z z k ( M 1 M 2 M 3 M 4 ) N iH i [ z : = I ] de modo a que R 0 é a composição Y I R z 0 [ z : = I ] I[z: =Eu]

R0 0z:Yzzk(M1M2M3M4)NEuMEu[z: =Eu]
R0 0YEuR0 0z[z: =Eu]Euk(N1N4)WkN1N4

REu:NEuN{Eu,W}

REuz:MEuNEuzREu:NEuREuz[z: =Eu]NEuz[z: =Eu]EuN

REuEuNEuz[z: =Eu]NNEuz

NEuzzNzNN{Eu,W}NEuz

zk1(λx.zk2(x))zk1(λW.zk2(zk3(zk5(zk7(W)zk8(λx.zk9(x)))zk6(W))zk4(W)))

M1M2M3M4N1zN2zN3zN4zNEuzzEuEu=1,2WEu=3,4

Ao mesmo tempo, o termo N1zN2zN3zN4z ainda deve reduzir para produzir a infinita fpc Bohm tree z(z(z())). Portanto, deve haver uma "aspersão"zkj em um dos NEuz que chega infinitamente frequentemente à cabeça do termo, mas não bloqueia reduções adicionais dele.

E agora terminamos. Inspecionando cadaNEuz, para Eu4e cada valor possível de kj, para j2+7Eu-12, descobrimos que não existe tal aspersão.

Por exemplo, se modificarmos o último W dentro EuEuWW Como Wz=λW.z(WEuWW), obtemos a redução de normalização

EuEuWWzEuWWzWWzWzEuWzWzz(EuEuEuEu)WzWzzEuWzWz

(Notar que Ωadmite tal aspersão precisamente porque um certo subtermo dele pode ser "protegido" sem afetar a não normalização. A variável vem na posição principal, mas redexes suficientes permanecem abaixo.)

3. A "transformação por aspersão" tem outros usos. Por exemplo, colocandoz na frente de cada redex em M, obtemos um termo N=λz.Mz que é uma forma normal, mas satisfaz a equação NEu=M. Isso foi usado por Statman em [2], por exemplo.

4. Como alternativa, se você relaxar o requisito de que YEu=M, você pode encontrar vários fpcs (fracos) Y que simulam a redução de M, enquanto produz uma cadeia de zs ao longo do caminho. Não tenho certeza se isso responderia à sua pergunta geral, mas certamente há várias transformações (computáveis)MYM que produzem combinadores de loop para cada mudo M, de tal maneira que o gráfico de redução de YM é estruturalmente semelhante ao de M. Por exemplo, pode-se escrever

YMz={z(YP[x: =Q]z)M(λx.P)QYNzM não é um redex e MWhN

[1] Severi P., de Vries FJ. (2011) Decompondo a Malha de Conjuntos Sem Significado no Cálculo Infinitário de Lambda. In: Beklemishev LD, de Queiroz R. (eds) Lógica, Linguagem, Informação e Computação. WoLLIC 2011. Notas de aula em Ciência da Computação, vol 6642.

[2] Richard Statman. Não há combinador hiper-recorrente S, K. Relatório de Pesquisa 91–133, Departamento de Matemática, Universidade Carnegie Mellon, Pittsburgh, PA, 1991.

Andrew Polonsky
fonte
Essa resposta é ótima e provavelmente vou aceitá-la. No entanto, não sei ao certo quais são os teoremas reais que você está descrevendo, exceto "não há combinador de loop"Y de tal modo que Y Eu=Ω3". Acho que declarar os teoremas separadamente tornará os argumentos muito mais fáceis de seguir.
Cody
Bom ponto. Acabei de atualizar a resposta.
Andrew Polonsky