Encontrar un umbral de tal manera que una función sea siempre más grande que la otra

cs.stackexchange https://cs.stackexchange.com/questions/118924

  •  28-09-2020
  •  | 
  •  

Pregunta

Dada la función recursivamente definida $ c $ : $$ C (m, n)=comienzan {casos} 0 & \ texto {para} m= 0 \\ n ^ 2 + n + 1 & \ texto {para} m= 1 \ texto {y} n \ ge 0 \\ C (M-1, 1) & \ texto {para} m> 1 \ texto {y} n= 0 \\ C (M-1, C (M, N-1)) & \ texto {para} m> 1 \ texto {y} n> 0 \\ \ End {casos} $$

y la función $ d $ :

$$ d (n)=underbrace {2 ^ {2 ^ {. ^ {. ^ {. ^ {. ^ {2}}}}}}} _ {\ texto {$ n + 2 $}} $$

Las entradas $ m $ y $ n $ son los números naturales. Me piden que encuentre un $ x $ , de modo que para todos los números $ y \ ge x $ , $ c (y, y)> d (y) $ .

Reescribí las dos funciones usando Python para calcular algunos valores:

 c(m, n):
    if m == 0:
        return 0
    else if m == 1 and n >= 0:
        return n**2+n+1              # return n^2+n+1
    else if m > 1 and n == 0:
        return c(m-1, 1)
    else if m > 1 and n > 0:
        return c(m-1, c(m, n-1))

 d(n):
    exp_num = n-1
    result = 2
    while exp_num != -1:
        result = 2**result           # result = 2^result
        exp_num = exp_num - 1
    final_result = 2**result         # final_result = 2^result
    return final_result

Algunas entradas y salidas:

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, un número con 19729 dígitos.

Creo que el umbral es de $ 3 $ , como c(3, 3) no parece ser realista computable teniendo en cuenta que son más de 19K dígitos en a (4, 2). Lamentablemente, no tengo idea de cómo probar esto. Cualquier ayuda sería muy apreciada.

¿Fue útil?

Solución

Como lo presenta, el umbral es de hecho 3.

Aquí hay un enfoque para demostrar que para todos los números $ y \ ge 3 $ , $ c (y, y )> D (y) $ .

Paso 0, muestra que $ c (\ cdot, \ cdot) $ está aumentando estrictamente con respecto a cada variable cuando la segunda variable no es 0.
Paso 1, muestra que $ c (1, n) \ gt n ^ 2 $ para todos $ n \ ge0 $ < / span>.
Paso 2, muestre que $ c (2, n) \ gt 2 ^ n $ para todos $ n \ ge0 $ < / span>.
Paso 3, Muestre que $ c (3, n) \ gt d (n) $ para todos $ n \ ge0 $ .
Paso 4, muestre que $ c (y, y) \ gt d (y) \ texto {if} y \ ge3 $ .


Ejercicio. Mostrar que $ C (3, y)> \ Subbrace {2 ^ {2 ^ {\ CDOT ^ {\ CDOT ^ {\ CDOT ^ 2}}}}} _ {2y + 2 \ texto {copias de} 2} $ para todos $ y \ ge0 $ .

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top