Um exemplo em que o menor termo lambda normal não é o mais rápido

12

Deixe o de -terms ser definido da seguinte maneira:λsizeλ

  • size(x)=1 ,
  • size(λx.t)=size(t)+1 ,
  • size(ts)=size(t)+size(s)+1 .

Permita que a complexidade de a λ -term t seja definida como o número de reduções beta paralelas de tx à sua forma normal (usando um avaliador ideal no sentido de Levy).

Estou procurando um exemplo de dois termos \ lambda normais para a mesma função em que o termo maior tem menor complexidade.λ

...

Editar para maior clareza

como parece que não é óbvio o que estou perguntando, tentarei dar um exemplo sólido. Costuma-se acreditar que a definição "ingênua" / "mais simples" de uma função é lenta e não ideal. Um melhor desempenho aumenta a complexidade do termo, pois você precisa adicionar estruturas de dados, fórmulas etc. Um ótimo exemplo é fibonacci, que pode ser "ingênuo" definido como:

-- The fixed fibonacci definition
fib_rec fib n =
    if (is_zero x) 
        then 1 
        else fib (n - 1) + f (n - 2)

-- Using church numbers instead of the λ-combinator to get a normal form
fib n = n fib_rec 0 n 

Isso é geralmente considerado como a definição "mais simples" de fib, e é muito lento (exponencial). Se expandirmos as dependências de fib(as definições usuais para adição de número de igreja, pred, is_zero) e normalizarmos, obteremos este termo:

fib = (λa.(a(λbc.(c(λdef.f)(λde.d)(λde.(de))
      (λde.(b(λfg.(c(λhi.(i(hf)))(λh.g)(λh.h)))
      d(b(λfg.(c(λhi.(i(h(λjk.(k(jf))))))(λhi.g)
      (λh.h)(λh.h)))de)))))(λbc.c)a))

Melhorias como tabelas de memorização tornariam esse termo maior. No entanto, existe um termo diferente que é muito menor ...

fib = (λa.(a(λb.(b(λcde.(e(λfg.(cf(dfg)))c))))
      (λb.(b(λcd.(cd))(λcd.d)))(λbc.b)))

e, curiosamente, também é assintoticamente superior ao ingênuo, correndo O(N). De todas as definições que tenho conhecimento, essa é a mais rápida e a mais simples . O mesmo efeito acontece com a classificação. Definições "ingênuas", como classificação de bolha e inserção, geralmente são expandidas para termos enormes (mais de 20 linhas), mas existe uma definição pequena:

-- sorts a church list (represented as the fold) of church numbers
sort = λabc.a(λdefg.f(d(λhij.j(λkl.k(λmn.mhi)l)(h(λkl.l)i))
       (λhi.i(λjk.bd(jhk))(bd(h(λjk.j(λlm.m)k)c))))e)(λde.e)
       (λde.d(λfg.g)e)c

O que também passa a ser mais rápido, assintoticamente, do que qualquer outra definição que eu conheça. Essa observação me leva a acreditar que, em oposição à crença comum, o termo mais simples, com a menor complexidade de Kolmogorov, geralmente é o mais rápido. Minha pergunta é basicamente se há alguma evidência do contrário, embora eu tenha dificuldade em formalizá-la.

MaiaVictor
fonte
3
Não possui complexidade sqrt (n). n!=n.n1....2.1
T ....
2
Tenho certeza de que você pode codificar a divisão de teste por um termo mais curto que o algoritmo AKS. λ
Emil Jeřábek 3,0
2
Concordo com @ EmilJeřábek e, na verdade, eu não vejo como um exemplo não é obtido por olhar para algoritmos de ordenação, como você já fez: não é o bolha -termo implementação tipo menor do que o -termo implmenting , digamos, tipo de pilha? Ou, eu não sei, uma pesquisa de força bruta, super curta para implementar, mas com tempo exponencial, em comparação com um algoritmo inteligente de polytime que exige mais linhas de código ...? Devo estar faltando alguma coisa, receio não entender realmente a pergunta. λλ
Damiano Mazza
1
Não fiz nenhum esforço para anotá-la, mas, como princípio heurístico, os comprimentos relativos de dois algoritmos geralmente não são afetados muito pela escolha da linguagem de programação, e não vejo absolutamente nenhuma razão -calculus deve ser uma exceção . Observe, em particular, que a normalização é um problema aqui: a maneira mais natural de expressar algoritmos no -calculus fornece termos normais desde o início e, de qualquer forma, IIRC da minha experiência com o Unlambda, você pode transformar qualquer termo em um termo normal de comprimento semelhante, dando o mesmo resultado quando aplicado. λλ
Emil Jeřábek 3,0
2
E sim, como Damiano menciona, a AKS era apenas um exemplo. O mesmo deve ocorrer em praticamente qualquer situação em que tenhamos um algoritmo ineficiente trivial e uma solução eficiente, mas muito mais sofisticada, do mesmo problema.
Emil Jeřábek 3,0

Respostas:

10

O teorema de aceleração de Blum é geralmente indicado na linguagem de funções parcialmente recursivas, mas até diferenças triviais na notação, funciona da mesma forma na linguagem -calculus.λ

Ele diz que, dada qualquer medida de complexidade razoável (por exemplo, o número ideal de reduções, como na pergunta) e uma função recursiva (por exemplo, ), podemos encontrar um predicado recursivo modo que:Mf(x,y)2yP(x)

Para cada algoritmo (isto é, -term na forma normal aqui) computando , existe outro algoritmo para que possui velocidade acima de : λgPhPfg

f(x,M(h,x))M(g,x) for all large enough inputs x,

onde indica a complexidade do cálculo do na entrada de acordo com a medir .M(g,x)gxM

Consequentemente:

  • P não possui algoritmo assintoticamente ideal na medida dada

  • em particular, o algoritmo mais curto para não é assintoticamente idealP

  • para qualquer algoritmo para , existe um algoritmo assintoticamente mais rápido, cuja forma normal é mais longa (porque até a renomeação de variáveis, há apenas muitos termos normais de um determinado comprimento)P

Emil Jeřábek 3.0
fonte