Tio Petros
Temas
Archivos
Enlaces
Matemáticas
Ciencia
Escepticismo
Bitácoras amigas
Divulgación
Estadísticas
Otros
Se muestran los artículos pertenecientes a Febrero de 2006.
Tan sólo dos párrafos rompiendo el plácido silencio de este blog en el ciberlimbo , ahora tan sólo interrumpido con las visitas y los comentarios de los lectores, para alegría y contento del autor. El primero para agradecer los ya más de cincuenta comentarios al cierre temporal del mismo. Siempre he dicho que los comentarios son la sal del blog, pero son mucho más: son el único feedback con el que cuenta el autor para saber si su trabajo está teniendo algún interés para los lectores, mucho más allá de la vaga pero también válida referencia de los contadores de visitas. Muchas gracias a todos por unos comentarios tan inmerecidamente positivos. El segundo para recomendarles el post que Vailima , ese pedazo de mujer con la que uno, sin mayor mérito por su parte, tiene la suerte y el gusto de compartir su vida; ha dedicado al escritor norteamericano Dan Brown. Pocas veces un autor ha merecido, en mi humilde opinión, un post de este calibre. Hasta pronto. Viene de aquí Pero la arena no escapa de ser contada, como Arquímedes reconoció en el tercer siglo A.C. Así es como él empezó El contador de arena, una especie de artículo de ciencia popular enviado al rey de Siracusa: Este Arquímedes procedió a hacer, esencialmente mediante el uso del antiguo término griego miríada, que significa diez mil, la base de los exponenciales. Adoptando el presciente modelo cosmológico de Aristarco, en el cual la "esfera de las estrellas fijas" es inmensamente mayor que la esfera en la que la Tierra gira alrededor del sol, Arquímedes obtuvo un límite superior de 1063 del número de granos de arena necesarios para llenar el universo. (Supuestamente 1063 es el mayor número con un nombre lexicográfico estándar americano: vigintillion (*). Pero el serio vigintillion tiene que velar para no ser usurpado por el más caprichosamente nombrado googol, o 10100, y googolplex, o 1010^100.) Vasto es, por supuesto, pero 1063 no es elevado a los altares del mayor número de todos los tiempos. Seis siglos después, Diofanto desarrolló una notación más simple para los exponenciales, permitiéndole sobrepasar 1010^10^10^10. Entonces, en la edad media, el alzamiento de los numerales árabes y el posicionamiento decimal hicieron fácil apilar exponenciales todavía mayores. Pero el paradigma de Arquímedes para expresar grandes números no fue fundamentalmente superado hasta el siglo veinte. E incluso hoy, los exponenciales dominan la discusión popular de lo inmenso. Considera, por ejemplo, la a menudo repetida leyenda del gran visir de Persia que inventó el ajedrez. El rey, como dice la leyenda, quedó encantado con el nuevo juego, e invitó al visir a pedir su propia recompensa. El visir replicó que, siendo un hombre modesto, sólo deseaba un grano de trigo por el primer cuadro del tablero, dos granos por el segundo, cuatro por el tercero, y así sucesivamente, con dos veces más granos por cuadro que el anterior. El anumérico rey consintió, sin darse cuenta que el número total de granos por todas las 64 casillas sería 264-1, or 18,4 trillones... equivalente a la actual producción mundial de trigo durante 150 años. Apropiadamente, es este crecimiento exponencial lo que hace al propio ajedrez tan difícil. Hay solamente sobre 35 elecciones lícitas en cada movimiento ajedrecístico, pero las elecciones se multiplican exponencialmente hasta producir sobre 1050 posibles posiciones en el tablero... demasiados incluso para que un ordenador las busque exhaustivamente. Eso es por lo que se tardó hasta 1997 que un ordenador, Deep Blue, derrotase al campeón mundial humano de ajedrez. Y en el Go, que tiene un tablero de 19×19 y sobre 10150 posibles posiciones, incluso un humano aficionado todavía puede derrotar los programas número uno del mundo. El crecimiento exponencial infecta los ordenadores también en otras guisas. El problema del viajero pregunta por la ruta más corta que conecte un conjunto de ciudades, dada la distancia entre cada par de ciudades. Lo irritante es que el número de rutas posibles crece exponencialmente según el número de ciudades. Cuando hay, digamos, un ciento de ciudades, hay sobre 10158 rutas posibles, y, aunque son posibles varios atajos, ningún algoritmo computacional conocido es fundamentalmente mejor que probar una a una cada ruta. El problema del viajero pertenece a una clase llamada NP-completa, que incluye cientos de otros problemas de interés práctico. (NP representa el término técnico `tiempo polinomial no determinístico’.) Es sabido que si hay un algoritmo eficiente para cualquier problema NP-completo, entonces hay algoritmos eficientes para todos ellos. Aquí `eficiente’ significa usando una cantidad de tiempo proporcional al tamaño máximo del problema elevado a alguna potencia fija, por ejemplo, el número de ciudades al cubo. Sin embargo, se conjetura que no existe ningún algoritmo eficiente para los problemas NP-completos. La prueba de esta conjetura, llamada P≠NP, ha sido un gran problema irresuelto de la ciencia computacional durante treinta años. Aunque los ordenadores probablemente nunca resolverán los problemas NP-completos eficientemente, hay más esperanza por otro grial de la ciencia computacional: la replicación de la inteligencia humana. El cerebro humano tiene aproximadamente cien mil millones de neuronas conectadas mediante cien billones de sinapsis. Y aunque la función de una neurona individual es sólo parcialmente entendida, se piensa que cada neurona despide impulsos eléctricos según reglas relativamente simples hasta mil veces por segundo. Así que lo que tenemos es un ordenador altamente interconectado capaz de quizá 1014 operaciones por segundo; en comparación, el más rápido superordenador paralelo del mundo, el 9200-Pentium Pro teraflops machine en Sandia National Labs, puede ejecutar 1012 operaciones por segundo. Contrariamente a la creencia popular, la materia gris no sólo está cableada para la inteligencia: sobrepasa al silicio incluso en puro poder computacional. Pero es improbable que esto permanezca cierto durante mucho tiempo. La razón es la ley de Moore, que, en su formulación de 1990, expresa que la cantidad de información almacenable en un chip de silicio crece exponencialmente, doblándose aproximadamente una vez cada dos años. La ley de Moore finalmente quedará fuera de juego, cuando los componentes del microchip alcancen la escala atómica y la litografía convencional vacile. Pero radicales nuevas tecnologías, tales como ordenadores ópticos, ordenadores de ADN, o incluso ordenadores cuánticos, podrían concebiblemente usurpar el lugar del silicio. El crecimiento exponencial en la potencia computacional no puede continuar para siempre, pero podría durar lo suficiente para que los ordenadores (al menos en poder de procesamiento) sobrepasen al cerebro humano. Para los pronosticadores de la inteligencia artificial, la ley de Moore es un glorioso heraldo del crecimiento exponencial. Pero los exponenciales también tienen su lado más sombrío. Recientemente la población humana pasó de los seis mil millones y se duplica cada cuarenta años aproximadamente. A esta razón exponencial, si una persona media pesa setenta kilos, entonces en el año 3750 la Tierra entera estará compuesta de carne humana. Pero antes de que inviertas en desodorantes, date cuenta de que la población parará de incrementarse mucho antes de esto ocurra, ya sea por hambrunas, epidemias, calentamiento global, extinciones en masa de especies, aire irrespirable, o, entrando en el reino de la especulación, control de natalidad. No es difícil comprender porqué el físico Albert Bartlett afirma que "la mayor limitación de la raza humana" es "nuestra incapacidad de entender la función exponencial". O porqué Carl Sagan nos aconseja "nunca subestimar una exponencial". En su libro Miles de millones, Sagan da otras deprimentes consecuencias del crecimiento exponencial. Al porcentaje inflacionario del cinco por ciento al año, un dólar valdría sólo 37 centavos después de veinte años. Si un núcleo de uranio emite dos neutrones, y ambos colisionan con otros dos núcleos de uranio, haciéndoles emitir dos neutrones, y así en adelante... bueno, ¿mencioné el holocausto nuclear como un posible fin del crecimiento poblacional? (*) En inglés americano un m-illón, en vez de ser 106m, es 103m+3. Sigue aquí Viene de aquí Los exponenciales son familiares, relevantes, íntimamente conectados con el mundo físico y los miedos y esperanzas humanos. Usando el sistema notacional que discutiré a continuación, podremos nombrar concisamente números que hacen insignificantes por comparación a los exponenciales, que subjetivamente hablando exceden 99^9^9 tanto como éste excede al 9. Pero estos nuevos sistemas podrían pareces más abstrusos que los exponenciales. En su ensayo Sobre el entumecimiento numérico, Douglas Hofstadter lleva a sus lectores al precipicio de esos sistemas, pero entonces asegura que: Pero dejar el tema es abandonar, no sólo el desafío del mayor número, sino cualquier esperanza de entender cómo los más fuertes paradigmas llevan a los más vastos números. Y así llegamos al temprano siglo veinte, cuando una escuela de matemáticos llamados formalistas buscan colocar toda la matemática sobre rigurosas bases axiomáticas. La pregunta clave para los formalistas fue qué significa la palabra `computable’. Es decir, ¿cómo podemos decir si una secuencia de números puede ser listada por un procedimiento mecánico definido? Algunos matemáticos pensaban que `computable’ coincidía con una noción técnica llamada `recursiva primitiva’. Pero en 1928 Wilhelm Ackermann los refutó construyendo una sucesión de números que es claramente computable, aunque crece demasiado rápidamente para ser una recursiva primitiva. La idea de Ackermann fue crear una procesión sin fin de operaciones aritméticas, cada una más potente que la anterior. Primero viene la suma. Segundo viene la multiplicación, que podemos pensarla como una suma repetida: por ejemplo, 5×3 significa 5 sumado a sí mismo 3 veces, o 5+5+5=15. Tercero viene la potenciación, que podemos pensarla como una multiplicación repetida. Cuarto viene... ¿qué? Bueno, tenemos que inventar una rara operación nueva, para la potenciación repetida. El matemático Rudy Rucker la llama `tetración’. Por ejemplo, `5 tetrado a 3’ significa 5 elevado a su propia potencia 3 veces, o 55^5, un número con 2185 dígitos. Podemos continuar. Quinto llega la tetración repetida: ¿podemos llamarla `pentación’? Sexto llega la pentación repetida: ¿`hexación’? Las operaciones continúan infinitamente, con cada una soportada por su predecesora para asomarse incluso más alta hacia el firmamento de los grandes números. Si cada operación fuese un sabor dulce, entonces la sucesión de Ackermann sería el catálogo de muestras, mezclando un número de cada sabor. Primero en la secuencia está 1+1, o (no contengas la respiración) 2. Segundo está 2×2, o 4. Tercero es 3 elevado a la tercera potencia, o 27. ¡Eh, estos números no son tan grandes! Cuarto es 4 tetrado a 4, o 44^4^4, que tiene 10154 dígitos. Si estás planeando escribir este número, mejor que empieces ahora. Quinto es 5 pentado a 5, o 55^...^5 con `5 tetrado a 4’ numerales en la pila. Este número es demasiado colosal para describirlo en cualquier término ordinario. Y los números se vuelven mucho mayores a partir de aquí. Esgrimiendo la sucesión de Ackermann, podemos dar palizas a oponentes sin estudios en el desafío de los mayores números. Pero necesitamos ser cuidadosos, dado que hay varias definiciones de la sucesión de Ackermann, no todas idénticas. Bajo el límite de tiempo de quince segundos, aquí está lo que yo podría escribir para evitar la ambigüedad: Profunda como parece, la sucesión de Ackermann tiene algunas aplicaciones. Un problema en un área llamada la teoría de Ramsey pregunta por la mínima dimensión de un hipercubo que satisface una cierta propiedad. La dimensión correcta se piensa que es 6, pero la más baja dimensión que nadie ha sido capaz de probar es tan enorme que sólo puede ser expresada utilizando la misma `aritmética rara’ que fundamenta la sucesión de Ackermann. En verdad, el Libro Guinness de los récords una vez listó esta dimensión como el mayor número jamás usado en una demostración matemática. (Otro contendiente para el título fue una vez el número de Skewes, sobre 1010^10^10^3, que surge en el estudio de cómo los números primos están distribuidos. El famoso matemático G. H. Hardy dijo sarcásticamente que el número de Skewes era "el mayor número que jamás ha servido para algún propósito definido en matemáticas".) Lo que es más, la cabalgata vivamente ascendente de Ackermann hace un cameo ocasional en la ciencia computacional. Por ejemplo, en el análisis de una estructura de datos llamada `Union-Find’, un término se multiplica por la inversa de la sucesión de Ackermann, significando, para cada número entero x, el primer número n tal que el n-ésimo número de Ackermann es mayor que x. La inversa crece tan lentamente como la sucesión de Ackermann original crece rápidamente; para todos los propósitos prácticos, la inversa es como máximo 4. Continua aquí14/02/2006
Rompiendo el plácido silencio en Tio Petros
20/02/2006
¿Quién puede nombrar el mayor número? (1/8)
Les presento una serie de unos ocho posts sobre un tema especialmente querido entre los amigos de las matemáticas, y varias veces mencionados en Tio Petros: el tema de los números grandes. El autor del texto es Scott Aaronson, 1999 y la traducción al castellano ha sido realizada con permiso expreso del autor por un habitual colaborador de Tio Petros: Jorge Alonso.
En un viejo chiste, dos nobles compiten en nombrar el mayor número. El primero, después de rumiar durante horas, proclamó triunfantemente “¡Ochenta y tres!”. El segundo, poderosamente impresionado, contestó “Tú ganas”. El desafío por el mayor número claramente no tiene sentido cuando los contendientes lo hacen por turnos. Pero ¿qué pasaría si los contendientes escribiesen sus números simultáneamente, ninguno conociendo el del otro? Para presentar una charla sobre “números grandes”, invité a dos voluntarios de la audiencia a intentar precisamente eso. Les dije las reglas:
Tenéis quince segundos. Utilizando la notación matemática normal, palabras inglesas, o ambas, nombrar un sólo número entero, no un infinito, en una tarjeta en blanco. Ser lo suficientemente precisos para que cualquier matemático moderno pueda determinar exactamente qué número habéis nombrado, consultando únicamente tu tarjeta y, si es necesario, la literatura publicada.
Así que los contendientes no pueden decir “el número de granos de arena en el Sahara”, porque la arena fluctúa hacia dentro y hacia fuera del Sahara con regularidad. Tampoco pueden decir “el número de mi oponente más uno”, o “el mayor número que nadie jamás pensó más uno”; de nuevo, están mal definidos, dado lo que nuestro razonable matemático tiene disponible. Dentro de las reglas, el contendiente que nombre el mayor número gana. ¿Estáis listos? Preparados. Ya. Los resultados de la contienda nunca son lo que yo esperaría.
Una vez, un chico de séptimo grado llenó su tarjeta con una cadena de sucesivos nueves. Como muchos otros principiantes de los grandes números, buscó maximizar su número poniendo un 9 en cada posición decimal. Si hubiera elegido el 1, más fácil de escribir que el curvado 9, su número podría haber sido millones de veces mayor. Sin embargo, todavía sería diezmado por la chica con la que se enfrentaba, que escribió una cadena de nueves seguida por un superíndice 999. ¡Ajá! Una potencia: un número multiplicado por sí mismo 999 veces. Dándome cuenta de su innovación, declaré la victoria de la chica sin preocuparme en contar los nueves de las tarjetas. E incluso el número de la chica podría haber sido mucho mayor todavía, si ella apilase el poderoso exponencial más de una vez. Coge 99^9, por ejemplo. Este behemot, igual a 9387 420 489, tiene 369 693 100 dígitos. Por comparación, el número de partículas elementales en el universo observable tiene escasamente 85 dígitos, más o menos. Tres nueves, cuando se apilan exponencialmente, ya nos elevan incomprensiblemente más allá de toda la materia que podemos observar... en un factor de aproximadamente 10369 693 015.
Notación decimal, potencias, exponenciales apilados: cada uno puede expresar los ilimitados grandes números, y en este sentido son todos ellos equivalentes. Pero los sistemas de notación difieren dramáticamente en los números que pueden expresar concisamente. Eso es lo que los quince segundos de tiempo límite ilustran. Lleva la misma cantidad de tiempo escribir 9999, 9999 y 99^9^9... todavía el primer número es cotidiano, el segundo astronómico, y el tercero hiper-mega astronómico. La clave al desafío de los mayores números no una rápida escritura, sino más bien un potente paradigma para la captura concisa de la gargantúa. Tales paradigmas son rarezas históricas. Encontramos agitación en la antigüedad, otra agitación en el siglo veinte, y no mucho en medio. Pero cuando una nueva forma de expresar concisamente grandes números emerge, es a menudo como un subproducto de una revolución científica mayor: matemáticas sistematizadas, lógica formal, ciencia computacional.
Revoluciones importantes, como cualquier partidario de Kuhn puede decirte, sólo ocurren bajo las correctas condiciones sociales. Así, la historia de los grandes números es la historia del progreso humano. Y aquí yace un paralelismo con otra historia matemática. En su notable e infravalorado libro Una historia de π, Petr Beckmann argumenta que la razón entre la circunferencia y el diámetro es “un singular espejo de la historia del hombre”. En las raras sociedades donde la ciencia y la razón encontraron refugio (la temprana Atenas de Anaxágoras e Hippias, la Alejandría de Eratóstenes y Euclides, la Inglaterra del siglo diecisiete de Newton y Wallis) los matemáticos dieron tremendos pasos en el cálculo de π. En Roma y en la Europa medieval, por constraste, el conocimiento de π se estancó. Rudas aproximaciones como el 25/8 de los babilónicos y el 3 de la biblia se mantenían alternantes.
Pienso que este mismo patrón se aplica a los grandes números. La curiosidad y la franqueza llevan a la fascinación por los grandes números, y al boyante punto de vista de que ninguna cantidad, sea el número de estrellas en la galaxia o el número de manos posibles en el bridge, es demasiado inmensa para que la mente lo enumere. Recíprocamente, la ignorancia y la irracionalidad llevan al fatalismo respecto a los grandes números. La biblia, por ejemplo, se refiere veintiuna veces a la supuesta incontabilidad de la arena. Mira en génesis 32:13 “Sin embargo tú me dijiste: Yo te haré el bien y haré tu descendencia como la arena del mar, tan numerosa que no se puede contar.” O hebreos 11:12 “numerosa como las estrellas del cielo e incontable como la arena de la orilla del mar”. Esta noción de que la multitud de granos de arena bien podría ser infinita, que es para la pasmada estupefacción pero no para la cuantificación, es antigua. El historiador Ilan Vardi cita la antigua palabra griega ψαμμκoσιoι, o ciento-arena, de significado coloquial tropecientos millones; así como un pasaje de la Oda olímpica II de Píndaro afirmando que “la arena escapa de ser contada”.
Sigue aquí
23/02/2006
¿Quién puede nombrar el mayor número? (2/8)
Hay algunos... que piensan que el número de arenas es infinito en multitud... y hay algunos otros que, sin considerarlo infinito, todavía piensan que ningún número ha sido nombrado que sea suficientemente grande para exceder su multitud... Pero yo intentaré mostraros [números que] exceden no sólo el número de la masa de arena igual en magnitud a la Tierra... sino también en una masa igual en magnitud al universo.
27/02/2006
¿Quién puede nombrar el mayor número? (3/8)
Si continuásemos nuestra discusión sólo un milisegundo más, nos encontraríamos justo en medio de la teoría de funciones recursivas y complejidad algorítmica, y eso sería demasiado abstracto. Así que dejemos el tema aquí mismo.
A(111), suc. Ackermann, A(1)=1+1, A(2)=2x2, A(3)=3^3, etc.
.