Un ejemplo donde el término lambda normal más pequeño no es el más rápido

12

Deje que los términos size de λ se definan de la siguiente manera:

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

Deje que la complejidad de un λ -term t se defina como el número de reducciones beta paralelas desde tx a su forma normal (utilizando un evaluador óptimo en el sentido de Levy).

Estoy buscando un ejemplo de dos términos \ lambda normales para la misma función donde el término más grande tiene menor complejidad.λ

...

Editar para mayor claridad

Como parece que no es obvio lo que pregunto, intentaré dar un ejemplo sólido. A menudo se cree que la definición "ingenua" / "más simple" de una función es lenta y no óptima. Un mejor rendimiento aumenta la complejidad del término, ya que necesita estructuras de datos adicionales, fórmulas, etc. Un buen ejemplo es fibonacci, que puede definirse "ingenuamente" 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 

Esto a menudo se considera como la definición "más simple" de fib, y es muy lenta (exponencial). Si ampliamos las dependencias de fib(las definiciones habituales para la suma de números de iglesia, pred, is_zero) y la normalizamos, obtenemos este término:

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))

Las mejoras, como las tablas de memorización, ampliarían este término. Sin embargo, existe un término diferente que es mucho más pequeño ...

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

y, curiosamente, también es asintóticamente superior al ingenuo, corriendo O(N). De todas las definiciones que conozco, esta es la más rápida y la más simple . El mismo efecto ocurre con sort. Las definiciones "ingenuas" como el ordenamiento de burbujas y el ordenamiento por inserción a menudo se amplían a términos enormes (más de 20 líneas de largo), pero existe una pequeña definición:

-- 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

Que también resulta ser más rápido, asintóticamente, que cualquier otra definición que conozco. Esta observación me lleva a creer que, a diferencia de la creencia común, el término más simple, con la menor complejidad de Kolmogorov, suele ser el más rápido. Mi pregunta es básicamente si hay alguna evidencia de lo contrario, aunque me resultaría difícil formalizarlo.

MaiaVictor
fuente
3
No tiene complejidad sqrt (n). n!=n.n1....2.1
T ....
2
Estoy bastante seguro de que puede codificar la división de prueba por un término más corto que el algoritmo AKS. λ
Emil Jeřábek
2
Estoy de acuerdo con @ EmilJeřábek y, en realidad, no lo veo como un ejemplo no se obtiene mirando algoritmos de ordenación, como ya lo hizo: no es el burbuja -term implementar especie más corto que el -term implmenting , digamos, ¿montón? O, no sé, ¿una búsqueda de fuerza bruta, muy corta para implementar pero tiempo exponencial, frente a un algoritmo inteligente de polytime que requiere más líneas de código ...? Debo estar perdiendo algo, me temo que realmente no entiendo la pregunta. λλ
Damiano Mazza
1
No hice ningún esfuerzo para escribirlo, pero como principio heurístico, las longitudes relativas de dos algoritmos generalmente no se ven muy afectadas por la elección del lenguaje de programación, y no veo absolutamente ninguna razón cálculo- debería ser una excepción . Tenga en cuenta en particular que la normalización es una pista falsa aquí: la forma más natural de cómo expresar algoritmos en -calculus proporciona términos normales desde el principio, y de todos modos, IIRC de mi experiencia con Unlambda, puede transformar cualquier término en un término normal de longitud similar que da el mismo resultado cuando se aplica. λλ
Emil Jeřábek
2
Y sí, como menciona Damiano, AKS fue solo un ejemplo. Lo mismo debería mantenerse en más o menos cualquier situación en la que tengamos un algoritmo trivial ineficiente y una solución eficiente pero mucho más sofisticada del mismo problema.
Emil Jeřábek

Respuestas:

10

El teorema de aceleración de Blum generalmente se establece en el lenguaje de funciones parcialmente recursivas, pero hasta diferencias triviales en notación, funciona igual en el lenguaje de cálculo .λ

Dice que dada cualquier medida de complejidad razonable (por ejemplo, el número óptimo de reducciones como en la pregunta) y una función recursiva (por ejemplo, ), podemos encontrar un predicado recursivo tal que:Mf(x,y)2yP(x)

Para cada algoritmo (es decir, -term en forma normal aquí) computando , hay otro algoritmo para que tiene velocidad sobre : λgPhPfg

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

donde indica la complejidad del cálculo de en la entrada según medir .M(g,x)gxM

Por consiguiente:

  • P no tiene un algoritmo asintóticamente óptimo en la medida dada

  • en particular, el algoritmo más corto para no es asintóticamente óptimoP

  • para cualquier algoritmo para , hay un algoritmo asintóticamente más rápido cuya forma normal es más larga (porque hasta el cambio de nombre de las variables, solo hay muchos términos normales de una longitud determinada)P

Emil Jeřábek
fuente