La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Archive for 29 mayo 2007

Sobrevivir el máximo tiempo en un agujero negro (o ¿y si los gemelos cruzan el horizonte de eventos?)

Posted by Carlos en mayo 29, 2007

Como es bien sabido, el horizonte de eventos de un agujero negro marca un punto de no-retorno. Si disponemos de una astronave con motores de la suficiente potencia, podemos aproximarnos cuanto queramos a este horizonte (por supuesto, en un agujero negro estelar las fuerzas de marea podrían destrozarnos si nos acercamos demasiado, pero en un agujero negro supermasivo no habría problema de este tipo) y escapar. Sin embargo, una vez se cruce el horizonte la singularidad que hay en su interior estará en nuestro futuro, y por muy potentes que sean los motores de la astronave, no podremos volver a cruzar hacia afuera el horizonte. Nuestro suerte está echada, y en un tiempo finito todo acabará. Este tiempo dependerá de la masa del agujero negro, de la velocidad inicial con la que se cruce el horizonte de eventos, y de cómo actuemos en su interior. Analicemos cualitativamente esto último, y veamos qué estrategia es la que permite maximizar el tiempo de supervivencia dentro del horizonte de eventos.

Black hole
Credit: Alfred Kamajian

Cuando hace unos días hablábamos de la paradoja de los gemelos, vimos cómo una trayectoria rectilínea en el espacio-tiempo de Minkowski hacía que el observador experimentara el mayor tiempo propio. Éste es básicamente el principio del envejecimiento extremo, y es esencial también en el caso del agujero negro. Evidentemente, el espacio-tiempo no es para nada plano en este último caso, pero el principio es generalizable gracias a una de las intuiciones clave que permitió a Einstein pasar de la Relatividad Especial a la Relatividad General. A grandes rasgos, la idea básica es que los efectos de la gravedad (y la curvatura que induce en el espacio-tiempo) pueden ser ignoradas por un observador en caída libre. Por ejemplo, si vamos en un ascensor y se rompe el cable, antes de matarnos experimentaremos una sensación de ingravidez: flotaremos en mitad del ascensor, y con nosotros todos los objetos que pudiera haber en su interior. Si el cuerpo sobre el que caemos es lo suficientemente masivo, notaremos fuerzas de marea: habrá una diferencia en el tirón gravitatorio entre nuestros pies y la cabeza, y los objetos a nuestro alrededor comenzarán a converger radialmente. Estos efectos serán despreciables si reducimos más nuestro ámbito de observación. Así, habrá un pequeño entorno local (cada vez más pequeño cuanto más nos acercamos al cuerpo masivo) en el que podemos suponer que el espacio-tiempo es plano, y emplear la Relatividad Especial. Una trayectoria rectilínea significa entonces localmente rectilínea (en el pequeño sistema de referencia en el que en cada momento sea aplicable la suposición de espacio-tiempo plano), aunque globalmente sea curva. Esta trayectoria es una geodésica, y en la misma es aplicable el principio del envejecimiento extremo.

¿Cómo se puede aplicar ese principio en esta situación? Imaginemos a los dos gemelos que caen a la vez en el agujero negro: uno no hace nada (va en caída libre), mientras que el otro acelera hacia afuera, y luego hacia adentro para volver a encontrarse con su hermano. Tal como era el caso en la paradoja de los gemelos clásica, el que ha ido en caída libre ha experimentado más tiempo propio que el otro. No compensa entonces hacer ese tipo de maniobras. Pero, ¿y si el gemelo que acelera hacia afuera no deja nunca de hacerlo? Tarde o temprano se encontrará con la singularidad, pero ¿le habrá merecido la pena en términos de maximizar su tiempo propio? La respuesta es: no. Esto es lo que Geraint F. Lewis y Juliana Kwan, de la Universidad de Sydney han analizado en un trabajo titulado

aceptado por publicación en Publications of the Astronomical Society of Australia. El resultado que se obtiene puede resultar en primera instancia anti-intuitivo, pero en el fondo no lo es. Básicamente, el máximo tiempo propio hasta la singularidad lo experimentará un observador en caída libre que cruce el horizonte con velocidad v=0, por lo que la estrategia óptima es acelerar hacia afuera hasta igualar la trayectoria que se seguiría en ese caso ideal, y parar de acelerar en ese momento, viajando en caída libre el resto del camino. Cualquier desviación de esta estrategia acelerando más de la cuenta resultará en un tiempo propio menor, ya que la dilatación temporal jugará en nuestra contra.

Hay que resaltar que el tiempo propio experimentado será en cualquier caso pequeño, salvo que hayamos caído en un agujero negro verdaderamente hipermasivo. Por poner un ejemplo, en un agujero negro de la masa del Sol tendríamos unos 15 microsegundos, y en un agujero negro como el que hay en el centro de la galaxia en torno a un minuto. No es demasiado, pero menos da una piedra.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Física, Matemáticas | Etiquetado: , , | 3 Comments »

Música para el domingo – Alive and Kicking (Simple Minds)

Posted by Carlos en mayo 27, 2007

El domingo es día de asueto, y nada mejor que un poco de música para amenizarlo. Por ejemplo, este fantástico tema de Simple Minds titulado “Alive and Kicking“. Simple Minds son sin duda parte de la banda sonora de los 80s, y no es casualidad que en el reciente (y magistral) anuncio de Coca-Cola hayan elegido otro tema suyo (“Don’t you forget about me“) como fondo musical. Tanto este último tema (que curiosamente no fue compuesto por ellos), como “Alive and Kicking” son auténticos iconos musicales de la década. Su estilo pop-rock vanguardista y la voz del vocalista Jim Kerr les da un cierto tono mitad épico, mitad New Romantic, que las ha convertido en auténticos himnos.

El vídeo de “Alive and Kicking” es también para no perdérselo, con los miembros del grupo interpretando entre montañas y cataratas (posiblemente de su Escocia natal). Da vértigo ver al bajista tocando a centímetros de un precipicio. ¡Que lo disfruten!

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Música, Naturaleza | Comentarios desactivados

¿Problemas con el ácido úrico? Toma café

Posted by Carlos en mayo 26, 2007

Ácido ÚricoEl ácido úrico es uno de las sustancias de desecho del metabolismo humano (es el producto final de oxidación en el metabolismo de las purinas) y suele hallarse en la sangre con una concentración de hasta 8.3 mg/dl -o lo que es lo mismo, ~494 µmol/l- en individuos sanos. Cuanto esta concentración aumenta, pueden empezar problemas de diferente tipo. El más común es la gota, una inflamación artítrica que afecta fundamentalmente a los hombres (>95% de los casos). También pueden producirse cristalizaciones de ácido úrico en los riñones, que pueden resultar en la formación de cálculos renales. Por todo ello, el control del nivel de ácido úrico en sangre es importante desde el punto de vista sanitario. Normalmente, suele haber factores congénitos en este tipo de patología, pero también se postula que la dieta y el estilo de vida puede influir en la misma.

En relación con lo anterior, resulta especialmente interesante un estudio de más de 12 años de duración cuyos resultados han sido recientemente publicados, y que estudia la relación de la gota con el consumo de café, té, y otras bebidas. Se trata de un trabajo de Hyon K. Choi y colaboradores titulado

y publicado en la revista Arthritis & Rheumatism. El estudio ha abarcado más de 45,000 hombres por encima de los 40 años al comienzo del mismo, y durante el mismo se han tomado datos de la ingesta de café, té, bebidas de cola o chocolate por parte de los sujetos. De esta población de estudio se han diagnosticado 757 casos de gota, y al correlacionar los mismos con el consumo de estas bebidas se ha llegado a resultados sumamente interesantes. El riesgo de gota es 40% inferior en sujetos que consumían 4 ó 5 tazas de café al día, y un 59% inferior para los que tomaban 6 o más (por supuesto, estamos hablando del café -si puede llamarse así- que se toma en los EE.UU.). Lo más curioso es que no hay dependencias significativas ni del consumo de té, ni de la ingesta total de cafeína, lo que sugiere que es alguna sustancia diferente de esta última -por ejemplo el ácido clorogénico, un potente antioxidante presente en el café- la responsable del efecto (de hecho, hay un modesta correlación con el consumo de café descafeinado).

A la luz de estos potenciales efectos beneficiosos del café, cabe recordar la anécdota (quién sabe si apócrifa) de la que Voltaire -ingente consumidor de café- fue protagonista. Cuando le advirtieron de que el café era un veneno lento, afirmó: “Debe serlo realmente; hace más de cincuenta años que lo tomo, y aún no me he muerto“.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Biología Molecular, Medicina, Química | Etiquetado: , , | 17 Comments »

Día del Orgullo Friqui 2007

Posted by Carlos en mayo 25, 2007

En honor del día del orgullo friqui, aquí va un vídeo idóneo para la ocasión: música de Weird Al Yankovic versionando “Pretty Fly” de The Offspring, e imágenes de anime japonés perfectamente sincronizadas. Hasta hay espadas láser… Puntuación alta en el friquímetro.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Comic, Geek, Música | 3 Comments »

La paradoja de los gemelos y las transformaciones de Lorentz

Posted by Carlos en mayo 25, 2007

Cuando hace unos días hablábamos de la paradoja de los gemelos, surgió la cuestión de cómo la geometría del espacio-tiempo de Minkowski hacía que dados dos eventos A y B, el segundo en el futuro del primero, una linea temporal recta entre los mismos experimentara un tiempo propio mayor que el de cualquier otra línea temporal no recta entre A y B. El análisis geométrico es muy elegante, pero lo vamos a dejar para una futura ocasión. Vamos a ver en su lugar un bosquejo del análisis desde un punto de vista algebraico, usando las transformaciones de Lorentz (de manera muy simplificada, ya que en realidad vamos a utilizar poco más que el factor de dilatación y la regla de composición de velocidades). En primer lugar, consideremos la figura inferior izquierda, que es (casi) la misma que figuraba en el apunte anterior sobre la paradoja de los gemelos.

Paradoja de los gemelos

Esta figura representa la situación desde el punto de vista del gemelo que se queda en casa. El gemelo astronauta viaja durante t años hacia un planeta lejano, y al llegar al mismo vuelve, empleando otros t años para ello. En total, según el gemelo sedentario, han transcurrido 2t años en la Tierra, y algunos menos en la nave espacial; concretamente, desde el punto de vista del gemelo en casa, para el viajero habrán transcurrido 2γt años, donde γ es el factor de dilatación temporal. Usando unidades en las que c = 1,

\gamma = \sqrt{1-v^2}

donde v es la velocidad del viajero. ¿Cómo es la situación desde otro punto de vista? Pensemos por ejemplo en otro observador en situación de movimiento uniforme que acompaña al viajero en su trayecto de ida, pero que nunca da la vuelta para regresar. Este observador estaría indicado por la línea magenta en la figura izquierda, y desde su punto de vista (compartido por el viajero sólo durante el trayecto de ida) la cosa es tal como se describe en la figura derecha: es la Tierra la que se aleja a velocidad v en todo momento. El viajero está en reposo con respecto a este observador hasta que decide dar la vuelta. En este sistema de referencia, esto tiene lugar tras γt años. En ese momento, el viajero se aleja del observador a gran velocidad. Dado que la velocidad de la Tierra es v para el observador, y la velocidad relativa del viajero con respecto a la Tierra -medida por cualquiera de los dos gemelos- es también v (con el signo apropiado en todos los casos), el observador aprecia como el viajero se aleja de él a velocidad 2v/(1+v2), tal como la regla de composición de velocidades relativistas indica. Cualitativamente, esto es claramente superior a v, y explica cómo aunque desde el punto de vista del observador el reloj de la Tierra va más lento que el suyo, el del viajero va todavía mucho más lento durante esa parte del recorrido.

¿Cuánto tiempo tarda el viajero en dar alcance a la Tierra? Desde el punto de vista de este observador, el diferencial de velocidad entre viajero y Tierra es v‘ = 2v/(1+v2) – v = (v-v3)/(1+v2), y la distancia inicial cuando el astronauta da la vuelta era d= γtv, por lo que el tiempo de alcance es t‘ = d/v = t(1+v2)/γ años. Durante este tiempo, el factor de dilatación temporal del viajero (medido por este observador) es

\gamma' = \sqrt{1-\frac{4v^2}{(1+v^2)^2}}

El tiempo experimentado por el viajero será entonces t” = γ’t‘, y simplificando un poco puede verse que

t''=\frac{t(1+v^2)}{\sqrt{1-v^2}}\sqrt{1-\frac{4v^2}{(1+v^2)^2}} = \frac{t(1-v^2) }{\sqrt{1-v^2}} = \gamma t

Sumando el tiempo del trayecto de ida (γt años) obtenemos efectivamente 2γt años como el tiempo transcurrido para el viajero. Por supuesto, este observador verá que la reunión de los hermanos se produce tras t(1+v2)/γ + tγ = 2t/γ años. El tiempo transcurrido según él en la Tierra es por lo tanto (2t/γ)γ=2t, como era de esperar.

Puede hacerse el mismo análisis para otro observador que acompaña al viajero durante el trayecto de vuelta. ¿Qué es lo que pasa entonces desde el punto de vista del viajero? comparte el análisis del primer observador durante los primeros γt años propios, y el análisis del segundo durante los últimos γt años. Esto supone que durante la fase de movimiento uniforme (en cualquiera de los dos sentidos) sólo “percibe” 2γ2t años en la Tierra (γ2t al inicio, y otros tantos al final). ¿Qué pasa con todo el tiempo que transcurre en la Tierra entre estos dos pequeños tramos? Para el viajero, este periodo intermedio transcurre durante el intervalo durante el que cambia su velocidad. Evidentemente, esto no quiere decir que el viajero “vea” los años pasar en un instante, ya que las señales desde la Tierra tardan un tiempo en llegar a él. Sin embargo, cuando haga cuentas para eliminar estos efectos, se dará cuenta de que ésa es la realidad para él.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Física, Matemáticas | Etiquetado: , | 5 Comments »

Ten cuidado con lo que deseas…

Posted by Carlos en mayo 22, 2007

…porque siempre hay un genio torpe dispuesto a retorcer la realidad para complacerte.

Por cierto, 4 friquipuntos para quien entienda el chiste de la tira cómica, 3 friquipuntos más para quien además lo encuentre gracioso, y 1 friquipunto adicional por cada teoría alternativa sobre los detalles de qué sucede en la última viñeta. ¿Cuál es tu puntuación?

Actualización: Un par de ideas sobre qué puede pasar cuando el genio satisface el oscuro deseo del poco avezado estudiante. Alguna de estas ideas provienen de un hilo de discusión en Cosmic Variance, donde vi por primera vez esta tira cómica. En primer lugar habría que ver cómo decide el genio hacer que el hidrógeno tenga 2 electrones de valencia, y luego ver a qué nivel se analiza el efecto que eso produce. Por ejemplo, sin cambiar ninguna constante física, el genio puede añadir un electrón a cada átomo de hidrógeno. El anión H- es una de las bases más fuertes, y reacciona exotérmicamente (1675 kJ/mol) al obtener un segundo protón y dar lugar a H2. El resultado sería en este caso “Boom”.

Por supuesto, lo anterior implica también que súbitamente el Universo tiene una carga neta negativa de magnitud gigantesca, lo que haría que cualquier aglomeración de materia que no fuera lo suficientemente masiva para vencer la repulsión electrostática sería despedazada. El Universo quedaría bañado por un mar de electrones, y posiblemente esto provocara una rápida expansión cósmica. Quizás entonces el resultado podría ser mejor descrito como “Bang”.

Claro que el genio puede intentar que el H- no sea realmente un anión, y para ello puede pensar en reducir a la mitad la carga del electrón (manteniendo constante la de los quarks). Por supuesto, para que esto no afecte a la carga de los demás elementos químicos, todos duplicarán su número de electrones, lo que alteraría todas sus valencias (nuevamente “Boom”); claro que al cambiar la carga del electrón, cambiarían posiblemente todos los orbitales, así como la constante de estructura fina. Esto último podría compensarse multiplicando la velocidad de la luz por 4. Un cambio súbito de este tipo sería quizás un “boom-bang”. También puede mantener fija la carga del electrón, y duplicar la de los quarks, lo que probablemente conduciría a despedazar los núcleos atómicos (“Boom”). En cualquier caso, estos cambios en las constantes físicas pueden alcanzarse haciendo que el Universo pase por efecto túnel a otro punto del paisaje antrópico (suponiendo que la Teoría de Cuerdas sea correcta), por lo que podríamos describir el proceso como “Bang”.

En fin, todo lo anterior sin ánimo de ser exhaustivo, y por supuesto sujeto a todo tipo de correcciones por parte de físicos, químicos, y demás gente de bien.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Ciencia, Comic, Física, Nanoposts, Nerd, Química, What-if | Etiquetado: | 26 Comments »

Música para el domingo – Come on Eileen (Dexys Midnight Runners)

Posted by Carlos en mayo 20, 2007

El domingo es día de asueto, y nada mejor que un poco de música para amenizarlo. Por ejemplo, este gran tema de Dexys Midnight Runners titulado “Come on Eileen“. Grabada en 1982, fue uno de los grandes éxitos de la década de los 80s. La canción es una mezcla perfecta de pop y folk. Precisamente los violines celtas y el banjo son fundamentales para el característico sonido del tema, para su pegadiza melodía, y sobre todo para guiar los diferentes cambios de ritmos durante la canción. El vídeo es también muy interesante; ambientado en un barrio industrial del Reino Unido, y con los miembros del grupo ataviados con petos (y sin camiseta, en un “homenaje a la axila” como alguien lo llegó a denominar) tiene cierto aire atemporal, y resulta bastante entretenido de ver. ¡Que lo disfruten!

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Música | 11 Comments »

Caos, no linealidad, y espontaneidad en el comportamiento de los insectos

Posted by Carlos en mayo 19, 2007

La aleatoriedad es sólo una medida de nuestra ignorancia sobre
las causas que provocan un determinado evento.

Pierre Simon Laplace (1749-1827), matemático francés

Hace unos días Pjorge recuperaba una reseña sobre un libro de John Searle en el se que abordaba el tema de la consciencia humana. A raíz de esta reseña, hubo un interesante mini-debate en el hilo de comentarios sobre si la consciencia humana era una propiedad
algorítmica o no, y elaborando sobre este tema, una de las consideraciones que surgió hacía referencia a la posibilidad de que organismos anteriores a los humanos en la cadena evolutiva tuvieran un comportamiento modelable algorítmicamente. Es algo que parece razonable (al menos me lo pareció en primera instancia), pero que puede que no sea tan trivial de asumir. Precisamente, a través de MarkCC he llegado a un artículo que analiza cuestiones muy relacionadas con las anteriores consideraciones. Se trata concretamente de un trabajo de Alexander Maye y colaboradores, titulado

que acaba de ser publicado hace un par de días en PLoS ONE (revista de acceso abierto). En este trabajo se estudia el comportamiento de la mosca de la fruta -uno de los sujetos favoritos de experimentación por parte de los biólogos- y se intenta modelar el mismo. La idea básica que podemos tener sobre estos insectos es que son seres fundamentalmente reactivos: su comportamiento se describiría mediante una asociación entre estímulos y acciones. Sin embargo, una ligera inspección revela que éste no es el caso, ya que no siempre se responde al mismo estímulo con la misma acción. La solución inmediata es suponer que hay algún efecto aleatorio, algún tipo de ruido blanco que afecta a la toma de deciciones, tal como se ilustra en la figura inferior.

Sistema reactivo
Source: A. Maye et al., PLoS ONE 2(5): e443, 2007

¿Es este modelo realista? Eso es lo que se ha pretendido analizar en este trabajo. Para ello se ha considerado un enfoque experimental en el que se aísla a las moscas de estímulos externos (una especie de tanque de privación sensorial), y se analiza su trayectoria de vuelo. De manera más precisa, se examina la distribución temporal de los cambios de dirección. Dado que los estímulos externos están controlados, esta distribución proporciona información muy valiosa sobre los mecanismos que controlan la toma de decisiones.

Los resultados del análisis son sumamente interesantes. En primer lugar, se descarta que el mecanismo subyacente en el cerebro de la mosca sea una función determinista afectada por ruido blanco: la desviación de la distribución de intervalos entre cambios de dirección con respecto a una simulación de una distribución de Poisson es significativa. La distribución real exhibe además algunas propiedades llamativas tales como una cola larga, una de las características distintivas de las leyes de potencias:

p(l) \sim l^{-\mu}

Concretamente, podría tratarse de una distribución de Lévy, que exhibe un régimen de ley de potencias en el extremo de la distribución. Este tipo de distribuciones suele surgir de la interacción entre varios subsistemas no-lineares. Lo más común es que se trate de procesos estocásticos sin memoria en los que cada valor de la secuencia temporal depende únicamente del anterior. Esta explicación sigue sin ser del todo satisfactoria sin embargo. Si se supone que las secuencias son el resultado de un sistema no-linear con dinámica caótica, y se calcula la dimensión fractal del atractor, se encuentran diferencias significativas entre los modelos puramente aleatorios, y los datos experimentales.

La conclusión de los autores es que en el cerebro de las moscas hay lo que denominan un iniciador, un proceso determinista altamente no-lineal y muy complejo. Dada la sensibilidad a las condiciones iniciales (característica básica de los sistemas caóticos), este iniciador sería el responsable del comportamiento aparentemente espontáneo de la mosca. Se tiene constancia por otra parte de que este tipo de comportamiento es evolutivamente favorable, tanto desde el punto de vista de la exploración en busca de alimento, como por la presión selectiva que introduce durante el proceso de apareamiento.

Iniciador
Source: A. Maye et al., PLoS ONE 2(5): e443, 2007

Es sorprendente la extraordinaria complejidad subyacente al comportamiento aparentemente simple de una mosca. En relación al debate anterior sobre mente y calculabilidad, esta complejidad no supone en principio que exista ningún proceso no computable. Sí es interesante considerar que el hecho de que exista este extraordinario nivel de complejidad en este tipo de organismos pone de alguna manera el listón muy alto para lo que podemos encontrarnos más arriba en la cadena evolutiva. Por otra parte, la presencia de este tipo de iniciadores con extrema sensibilidad a las condiciones iniciales puede conducir a pensar (o al menos a no descartar) que incluso pequeñas desviaciones debidas a fenómenos cuánticos afecten de manera significativa al comportamiento emergente del organismo.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Calculabilidad, Inteligencia Artificial, Matemáticas, Zoología | 8 Comments »

Turing en una cáscara de nuez: castores afanosos y la paradoja de Berry

Posted by Carlos en mayo 15, 2007

Siguiendo la serie sobre computabilidad, hoy nos vamos a fijar en una función muy interesante, y que nos va a servir de nexo entre computación e información. Se trata de la función castor afanoso (busy beaver en inglés), y que podemos definir informalmente como el mayor valor que un algoritmo de cierto tamaño puede producir. De manera más precisa, supongamos un cierto formalismo para describir algoritmos, y consideremos una función que cuantifique el tamaño de una cierta descripción. Por ejemplo, podemos considerar máquinas de Turing con un alfabeto binario, y usar el número de estados como indicación del tamaño, o un cierto lenguaje de programación de alto nivel, y emplear como medida de tamaño de un programa su número de símbolos o de instrucciones (la elección que hagamos afecta a los valores particulares de la función, pero no a su esencia). Una vez tenemos esto, si A es un cierto algoritmo (que computa una función definida para el valor de entrada 0), emplearemos |A| para indicar su tamaño. Ahora, definimos la función Σ(n) como

\Sigma(n) = \max\{A(0)\ :\ |A|=n\}

esto es, el mayor valor computable por un algoritmo cuya descripción tiene una cierta complejidad (también se puede considerar alternativamente S(n), el mayor número de pasos que realiza un algoritmo de tamaño n antes de detenerse). Consideremos en primer lugar que se trata de una función que crece muy rápidamente. Por ejemplo, cuando hablamos de números grandes dimos una descripción muy concisa del número de Graham (una cantidad cuyo tamaño es simple y llanamente aberrante). Es posible entonces construir un algoritmo relativamente simple que lo calcula (no habría evidentemente forma de almacenarlo ni en un trillón de universos, pero ésa no es la cuestión), lo que evidencia que incluso para valores pequeños del parámetro de entrada, la función Σ(n) devuelve valores astronómicos. Consideremos por otra parte que se trata de una función bien definida: para cada tamaño n, hay un cierto algoritmo que calcula el valor más grande (o varios empatados, que para el caso es lo mismo). Por supuesto, dado un tamaño n hay programas que no se detienen, y que no nos interesan. Dado que el problema de la parada no es computable, por aquí podemos a empezar a ver la dificultad que plantea esta función. De hecho, la función Σ(n) no es computable.

Antes de ver una demostración formal de porqué no es computable esta función, resulta interesante considerar la paradoja de Berry. Esta paradoja se puede plantear de diferentes formas, pero consideremos la siguiente:

Uno más que el mayor número expresable con menos de veinte palabras.

Es fácil ver que esta expresión tiene menos de veinte palabras, y que supuestamente representa un número x. Sin embargo, de ser así, este número x sería estrictamente mayor que el máximo valor del conjunto de todos los números expresables con menos de veinte palabras, conjunto al que el propio x pertenece, lo que resulta en una contradicción. Esta paradoja es en el fondo el motivo por el que la función castor afanoso no es computable. De manera más precisa, supongamos que Σ(n) es computable. Podemos entonces definir una función M como sigue:

M(n) = \Sigma(2n)+1

Sea |M|=w. Definamos ahora Fw(n) como

F_w(n) = M(n+w)

Podemos asumir que |Fw|=2w (por ejemplo, sumar w puede hacerse mediante w instrucciones de incremento). Por la propia definición de la función Σ(n) tenemos que cuando n=2w

\Sigma(2w) \geqslant F_w(0) = M(w) = \Sigma(2w)+1

Llegamos a una contradicción, lo que invalida nuestra suposición inicial de que Σ(n) era computable. La demostración de incalculabilidad de S(n) es más simple todavía, ya que si sabemos el número máximo de pasos que da una máquina de complejidad n antes de detenerse, podemos determinar si una máquina arbitraria se para o no, simplemente simulándola durante dicho número de pasos: si no se para al llegar a ese límite, ya sabríamos que no se pararía nunca.

Tal como apuntaba al principio, uno de los aspectos más relevantes de esta función es como relaciona la complejidad de la descripción de un programa con lo que éste puede calcular. El próximo día habrá ocasión de profundizar en esta relación, que ofrece algunos resultados sumamente interesantes.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Calculabilidad, Matemáticas | 3 Comments »

Música para el domingo – Had a Dream (Roger Hodgson)

Posted by Carlos en mayo 13, 2007

El domingo es día de asueto, y nada mejor que un poco de música para amenizarlo. Por ejemplo, este espectacular tema de Roger Hodgson de 1984 titulado “Had a Dream (Sleeping with the Enemy)“. Esta canción forma parte del primer álbum en solitario de Roger Hodgson tras dejar Supertramp, y demuestra hasta qué punto su talento era la locomotora del grupo. Se trata de un tema vibrante, más cercano al rock clásico que al pop-rock progresivo de los últimos años de Supertramp, y que llegó a ser uno de los éxitos de aquél año. A esto contribuyó sin duda un vídeo magnífico, lleno de fuerza, con un gran manejo del color, y con algunas referencias cinematográficas claras. Todo un espectáculo visual. ¡Que lo disfruten!

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Música | 3 Comments »