miércoles, 18 de marzo de 2009

¿Quién puede nombrar el número más grande?

Imagínate un juego, el chiste es escribir el número más grande que puedas imaginar. Tienes una hoja, un lápiz y un contendiente que tratará de escribir un número más grande que el tuyo. ¿qué escribirías?

De niño yo escribiría una hilera de puros 9s hasta llenar la hoja. Después, descubres que hay números aún más grandes y que los puedes expresar con términos exponenciales. En el artículo Who can name the biggest number?, Scott Aaronson plantea esa pregunta ¿cuál es el número más grande que el humano ha calculado?

Es tan natural para nosotros hablar de números grandes, que parecería una tarea sencilla. ¿Cuántas neuronas tenemos en el cerebro?, se han hecho estudios que dicen que trillones. Los números grandes están en todos lados de la naturaleza y en nuestro propio organismo por supuesto.

En los juegos como el ajedrez, el número de posibles tableros es un número relativamente grande. Y es cuando entra la computación en el juego de los números grandes. Ciertamente muchos números han sido calculados con ayuda de las computadoras. Aún así existen muchos otros problemas con números grandes que son imposibles de resolver con la ayuda de las computadoras.

Por ejemplo, la función de Ackermann, es un clásico ejemplo de que un problema no es tratable. Los números de Ackermann crecen muchísisisisimo más rápido que cualquier función exponencial. Calcular un número de estos es intratable para incluso números pequeños, tan solo calcular Ackermann(4,2) ya es imposible para una computadora ordinaria.

¿Existirán números aún más grandes que crezcan aún más rápido que la función de Ackermann? La respuesta es sí, the Busy Beaver Number. Este número tiene que ver con máquinas de Turing. Se sabe que estos números existen, pero resulta que no son computables.

Imagínense, si conociéramos BB(n) (el n-ésimo Busy Beaver) tendríamos la capacidad para saber si un programa para con una entrada, en pocas palabras podríamos del alguna predecir el futuro.

Actualmente con los modelos de cómputo que han sido propuestos están muy limitados, sólo una pequeñisisima parte de los problemas existentes son posibles de resolver. La pregunta es, ¿tendremos que crear nuevos modelos de cómputo para atacar por otro lado a la solución de problemas grandes?

Les recomiendo leer este artículo, realmente habla de cosas muy interesantes . Y cuándo te pregunten cual es el número más grande escribe BB(6).

9 comentarios:

Miriam dijo...

ya lo lei ya lo lei :D,me parecio muy interesante ese artículo.

jsoffer dijo...

"Dos piedras construyen dos casas. Tres piedras construyen seis casas. Cuatro piedras construyen veinticuatro casas. Cinco piedras construyen ciento veinte casas. Seis piedras construyen setecientas veinte casas. Siete piedras construyen cinco mil cuarenta casas. De aquí en adelante, ve, y calcula lo que la boca es incapaz de decir, y lo que el oído es incapaz de escuchar"

-- Sefer Yetzirah, haciendo el salto de los factoriales a los no computables.

Memo dijo...

así es, otro problema intratable, tan fácil que se ve esa función factorial

Luis Eduardo dijo...

Memo, quién iba pensar que la función de Ackerman que nos pusieron en un examen de programación avanzada era algo más que una función recurrente.

Por cierto, no entendí muy bien esta parte y te lo comento no por mala onda, sino porque me quedé picado Jajajaja

"Imagínense, si conociéramos BB(n) (el n-ésimo Busy Beaver) tendríamos la capacidad para saber si un programa para con una entrada, en pocas palabras podríamos del alguna predecir el futuro. "

Saludos y que estés muy bien!

Memo dijo...

Lalo, gracias por escribir. The Busy Beaver Number es un problema que se planteó un matemático, se preguntó sobre cuál es el número máximo de pasos que tendría que realizar cualquier máquina de Turing con n reglas (imagínate el producto cartesiado del lenguaje de la cinta, por el número de estados). Esos números sí existen.
Pero si sabemos ese número, entonces podemos predecir si una máquina va a parar dada una entrada (Halting Problem), cosa que sabemos que no es cierta, por lo menos no podemos calcular ese número con una máquina de Turing.

Memo dijo...

Imagínense que ya tenemos ese número, entonces probamos nuestra máquina de Turing con n reglas, y si no para en BB(n) pasos sabremos que no terminará nunca...

Saúl dijo...

yo tengo la versión geek de tu respuesta cuando niño:

while(1)
print "9";

no hay buffers que desbordar :D

por otro lado, interesante lo que escribes, le daré una leidita al artículo que recomiendas, son justo los problemas que me gustan. Saludos, memito.

Luis Eduardo dijo...

Gracias por explicar Memo, me queda muy claro. A ver cuándo vamos a comer para que me enseñes qué tan volado estás ahora. Por cierto, qué mala onda lo de la camioneta que según ganaste. Quién sabe de dónde sacan los teléfonos estos tipos... Suerte!

Diego dijo...

Bastante interesante este ensayo que compartes, una vez más quedé fascinado por la vastedad de las matemáticas.

Saludos!