El argumento diagonal de Cantor es conocido de todos los matemáticos, y de gran parte de la gente que se dedica a disciplinas afines: física, ingeniería, etc.
En primer lugar expondré el argumento ee Cantor, y luego me dedicaré a discutir su utilidad
Tengamos los números reales entre 0 y 1 ordenados en una tabla, de tal manera que se pueda trazar una aplicación biyectiva entre los naturales y los reales entre 0 y 1.
0,143201
0,121234
0,132114
0,123345
0,124654
0,134766
Imaginemos que esta lista sigue hasta el infinito…Será entonces posible construir un nuevo número real comprendido en el intervalo entre 0 y 1 por el procedimiento de colocar en el lugar de la primera cifra decimal del primer número 1+1 en el lugar de la segunda del segundo número 2+1, en el lugar de la tercera cifra del tercer número 2+1, y así sucesivamente. Pero este número real no sería ya idéntico a ninguno de los incluidos en la tabla, ya que es distinto de cada uno de ellos, por lo menos en una cifra decimal. Veámoslo con números
El número 0,233467... no puede estar en ningún lugar de la lista, porque difiere del primer número en la primera cifra, del segundo en la segunda, del tercero en la tercera, etc. Pero, supongamos que en la lista hemos puesto todos los números reales entre 0 y 1 ¡nuestro nuevo número no estará en la lista! Esto significa que el intervalo de los números reales comprendido entre 0 y 1 es no numerable (es un infinito mayor que el de los números naturales).
Por muy esotérico que parezca el argumento de Cantor, lo cierto es que se utiliza con gran frecuencia en disciplinas como la lógica y la teoría de computación.
Leyendo librops como Computability de Cutland, Lógica para matemáticos de A. G: Hamilton, El desarrollo de la lógica de los Kneale,o incluso el libro de divulgación Gödel, Escher, Bach de Hofstadter, uno se da cuenta de la ubicuidad de las demostraciones de tipo diagonal.
Por ejemplo la demostración de que existen funciones que no son recursivas primitivas, o la demostración de que el conjunto de las funciones recursivas totales no es recursivamente enumerable.
Lo que es más, hay teoremas importantes, como el problema de la detención de la máquina de Turing o el teorema de Gödel ¡que también usan argumentos de tipo diagonal!
La paradoja de Russell también utiliza una especie método diagonal (aunque en este caso, el carácter diagonal del razonamiento resulta, seguramente, menos obvio).
Otras demostraciones, como la existencia de números reales no computables (debida a Turing) o la demostración de que existen gramáticas que van más allá de las que producen los autómatas finitos, si bien no utilizan el método diagonal ¡utilizan el conceptpo de conjunto no numerable de Cantor!
Así, resulta sorprendente, el hecho de que teorías matemáticas tan esotéricas como las de Cantor tengan una aplicación en campos mucho más prácticos como la teoría de computación y la informática.
(La teoría de Cantor ha sido extremadamente controvertida. No obstante, si prescindiéramos de ella, habría que amputar una parte muy importante de los hallazgos de la lógica a lo largo del siglo XX).
domingo, 9 de agosto de 2009
lunes, 18 de mayo de 2009
Las matemáticas y "Los crímenes de Oxford"
La fenomenal película Los crímenes de Oxford trata (entre otras cosas) el tema de las series matemáticas. Los tests para medir el CI suelen utilizar series de números.
Por ejemplo, ¿cuál es el siguiente término de esta serie?
1, 2.....
Fácil, ¿no? la mayoría de nosotros propondría 1, 2, 3 (la serie aritmética). Ahora bien, también podría ser 1, 2, 4 (la serie geométrica). Y también podría ser 1, 2, 6 (esta serie se calcula a partir del factorial, 1!, 2!, 3!, es decir 1, 1·2, 1·2·3...). También podríamos tener la serie 1, 2, 9 (1⁰,2¹, 3²...), , o la serie 1, 2, 5 (1, 1+1, 1+2+2,1+3+3+3,...) etc.
De hecho, existe un método, la intepolación de Lagrange, por el cual, para n puntos, siempre se puede escribir una ecuación que pase por esos n puntos.
¿Cómo distinguir, entonces, si un conjunto de n puntos obedecen a una ley o están situados al azar?
Gregory Chaitin escribió lo siguiente:
"If the law has to be extremely complicated[...]then the points are placed at random,[...] not in accordance with a scientific law. But if the law is simple, then it's a genuine law of nature, we are not fooling ourselves".
Conviene tener en cuenta esta teoría de Gregory Chaitin.
Dentro de las series de números naturales, uno de los subconjuntos es la de las series módulo 10. Para obtener las series módulo 10, cojemos las series normales, y, al 15 lo convertimos en 5, al 20 en 0, al 134 en 4, etc.
Como las series módulo 10, constan de un número infinito de términos, cada serie módulo 10 es biyectable con un número real.
Pero los números reales entre 0 y 1 son no computables con probabilidad 1. Es decir que la mayoría de los reales entre 0 y 1 no son computables. Sólo un número infinitesimal de los reales entre 0 y 1 son computables.
Por tanto, de entre las series infinitas de números naturales, sólo una cantidad infinitesimal de ellas es computable. La mayoría de series de números reales son aleatorias, en el sentido que da Chaitin a esta palabra.
Por ejemplo, ¿cuál es el siguiente término de esta serie?
1, 2.....
Fácil, ¿no? la mayoría de nosotros propondría 1, 2, 3 (la serie aritmética). Ahora bien, también podría ser 1, 2, 4 (la serie geométrica). Y también podría ser 1, 2, 6 (esta serie se calcula a partir del factorial, 1!, 2!, 3!, es decir 1, 1·2, 1·2·3...). También podríamos tener la serie 1, 2, 9 (1⁰,2¹, 3²...), , o la serie 1, 2, 5 (1, 1+1, 1+2+2,1+3+3+3,...) etc.
De hecho, existe un método, la intepolación de Lagrange, por el cual, para n puntos, siempre se puede escribir una ecuación que pase por esos n puntos.
¿Cómo distinguir, entonces, si un conjunto de n puntos obedecen a una ley o están situados al azar?
Gregory Chaitin escribió lo siguiente:
"If the law has to be extremely complicated[...]then the points are placed at random,[...] not in accordance with a scientific law. But if the law is simple, then it's a genuine law of nature, we are not fooling ourselves".
Conviene tener en cuenta esta teoría de Gregory Chaitin.
Dentro de las series de números naturales, uno de los subconjuntos es la de las series módulo 10. Para obtener las series módulo 10, cojemos las series normales, y, al 15 lo convertimos en 5, al 20 en 0, al 134 en 4, etc.
Como las series módulo 10, constan de un número infinito de términos, cada serie módulo 10 es biyectable con un número real.
Pero los números reales entre 0 y 1 son no computables con probabilidad 1. Es decir que la mayoría de los reales entre 0 y 1 no son computables. Sólo un número infinitesimal de los reales entre 0 y 1 son computables.
Por tanto, de entre las series infinitas de números naturales, sólo una cantidad infinitesimal de ellas es computable. La mayoría de series de números reales son aleatorias, en el sentido que da Chaitin a esta palabra.
sábado, 22 de noviembre de 2008
Keynes y la crisis de la bolsa
Hay un pasaje muy bueno de Keynes sobre el tema de la especulación en la bolsa.
Estas tendencias son una consecuencia difícilmente eludible de que hayamos logrado organizar unos mercados de inversiones "líquidos". Generalmente se admite que, en interés público, los casinos deben ser inaccesibles y costosos, y tal vez eso mismo sea cierto en el caso de las bolsas de valores. El hecho de que los pecaos de la bolsa de valores de Londres sean menos que los de Wall Street, quizá no se deba tanto a las diferencias en el carácter nacional, como a la circunstancia de que, para el inglés de tipo medio, Throgmorton Street es inaccesible y muy costosa en comparación con Wall Street para el mismo tipo de norteamericano. La comisión del corredor de bolsa, los fuertes cargos de los comisionistas y el pesado impuesto sobre operaciones o traslado de títulos que se paga a la Tesorería, gastos todos estos que acompañan a las operaciones en la bolsa de Londres reducen la liquidez del mercado[...] lo bastante para eliminar gran parte e las características de Wall Street. La implantación de un impuesto fuerte sobre todas las operaciones de compraventa podría ser las mejor reforma disponible con el objeto de mitigar en Estados Unidos el predominio de la especulación sobre la empresa.
El espectáculo de los mercados de inversión modernos me ha llevado algunas veces a concluir que la compra de una inversión debe ser permanente e indisoluble, como el matrimonio, excepto por motivo de muerte o de otra causa grave, y esto será un remedio útil para nuestros males contemporáneos; porque tal cosa forzaría a los inversionistas a dirigir su atención solamente a las oportunidades a largo plazo; pero un pequeño examen de este recurso nos lleva a un dilema, y nos muestra cómo la liquidez de los mercados de inversión a menudo facilita, aunque algunas veces impide, el curso de nuevas inversiones. Porque el hecho de que cada inversionista individual se haga la ilusión de que su compromiso es "líquido" (aunque esto no puede ser cierto para todos) calma sus nervios y lo anima mucho más a correr el riesgo
La idea más interesante de este pasaje es la siguiente: todos los inversionistas creen que podrían convertir su inversión en líquido. Pero esto no es posible.
Si todo el mundo quiere vender sus acciones la bolsa se desploma. Si todo el mundo quiere sacar el dinero de sus depósitos, los bancos se hundirán.
El capitalismo sobrevive porque la gente tiene la "ilusión" de la liquidez.
El capitalismo funciona mientras la gente tiene confianza en el capitalismo, y en el funcionamiento de los mercados.
En este sentido, el capitalismo no puede resistir sin cierto carácter "especulativo".
Todo el tinglado está basado en que la gente no va a vender todas sus acciones y a sacar todo el dinero de sus cuentas al grito de "maricón el último".
Pero estas cosas mejor no contarlas a nadie. Porque, como la gente pierda confianza en el capitalismo, nos vamos todos a la porra.
Estas tendencias son una consecuencia difícilmente eludible de que hayamos logrado organizar unos mercados de inversiones "líquidos". Generalmente se admite que, en interés público, los casinos deben ser inaccesibles y costosos, y tal vez eso mismo sea cierto en el caso de las bolsas de valores. El hecho de que los pecaos de la bolsa de valores de Londres sean menos que los de Wall Street, quizá no se deba tanto a las diferencias en el carácter nacional, como a la circunstancia de que, para el inglés de tipo medio, Throgmorton Street es inaccesible y muy costosa en comparación con Wall Street para el mismo tipo de norteamericano. La comisión del corredor de bolsa, los fuertes cargos de los comisionistas y el pesado impuesto sobre operaciones o traslado de títulos que se paga a la Tesorería, gastos todos estos que acompañan a las operaciones en la bolsa de Londres reducen la liquidez del mercado[...] lo bastante para eliminar gran parte e las características de Wall Street. La implantación de un impuesto fuerte sobre todas las operaciones de compraventa podría ser las mejor reforma disponible con el objeto de mitigar en Estados Unidos el predominio de la especulación sobre la empresa.
El espectáculo de los mercados de inversión modernos me ha llevado algunas veces a concluir que la compra de una inversión debe ser permanente e indisoluble, como el matrimonio, excepto por motivo de muerte o de otra causa grave, y esto será un remedio útil para nuestros males contemporáneos; porque tal cosa forzaría a los inversionistas a dirigir su atención solamente a las oportunidades a largo plazo; pero un pequeño examen de este recurso nos lleva a un dilema, y nos muestra cómo la liquidez de los mercados de inversión a menudo facilita, aunque algunas veces impide, el curso de nuevas inversiones. Porque el hecho de que cada inversionista individual se haga la ilusión de que su compromiso es "líquido" (aunque esto no puede ser cierto para todos) calma sus nervios y lo anima mucho más a correr el riesgo
La idea más interesante de este pasaje es la siguiente: todos los inversionistas creen que podrían convertir su inversión en líquido. Pero esto no es posible.
Si todo el mundo quiere vender sus acciones la bolsa se desploma. Si todo el mundo quiere sacar el dinero de sus depósitos, los bancos se hundirán.
El capitalismo sobrevive porque la gente tiene la "ilusión" de la liquidez.
El capitalismo funciona mientras la gente tiene confianza en el capitalismo, y en el funcionamiento de los mercados.
En este sentido, el capitalismo no puede resistir sin cierto carácter "especulativo".
Todo el tinglado está basado en que la gente no va a vender todas sus acciones y a sacar todo el dinero de sus cuentas al grito de "maricón el último".
Pero estas cosas mejor no contarlas a nadie. Porque, como la gente pierda confianza en el capitalismo, nos vamos todos a la porra.
martes, 24 de junio de 2008
Economía y ecología
Continuamente oímos hablar del mal que hace el hombre al entorno natural. A veces surgen autores que tratan el tema de una forma optimista, como lo hace Bjorn Lomborg en su libro "El ecologista escéptico".
Sin embargo los optimistas olvidan dos factores:
1) que el crecimiento de la población, se ha acelerado de tal manera en los últimos siglos que ha pasado de ser lineal a exponencial.
2) que la gente demanda, en todas partes, cada vez más bienes de consumo.
Como la población sigue creciendo, y como el número de objetos de consumo que tiende a desear cada persona es virtualmente infinito, no hace falta ser un genio para darse cuenta de que caminamos hacia la catástrofe.
Yo creo que hay dos posibilidades:
a) que acabemos comiéndonos a los humanos
b) un gobierno mundial que controle la natalidad y se encargue de que se produzcan las cosas verdaderamente necesarias, en vez de anegarnos en un mar de mierda (con perdón).
Mucha gente objetará que el gobierno mundial es algo utópico. Bien, puede ser. Pero alguien como Bertrand Russell (que no puede ser reputado de imbécil) proponía el gobierno mundial para salvarnos de la guerra nuclear. Hoy, con la crisis ecológica, un gobierno mundial sería aún más necesario.
Lo cierto es que gran parte de las cosas que se consumen son basura. Había una serie británica de los años 70, "Caída y auge de Reginald Perrin" en que un tío se hacía rico vendiendo basura.
Libros como la "Teoría de la clase ociosa" de Veblen o "La sociedad opulenta" de Galbraith sostienen que el capitalismo se dedica a producir un montón de bienes, muchos de los cuales son inútiles, pero sirven para demostrar el status superior de quien los consume.
Si no hay un goierno mundial, al menos debería haber un acuetdo mundial para controlar la natalidad y la producción
Hay quien cree que a mayor población, mayor número de productores,y por tanto mayor prosperidad.
Bien. Eso sería cierto si los recursos o materias primas fueran infinitos.
Lo curioso es que la mayoría de economistas razonan como si los recursos fueran inagotables.
Cuando alguien (como Galbraith) discrepa de la opinión general, lo tachan de hereje, y ni siquiera lo consideran economista.
La única forma de evitar el desastre es limitar la natalidad y mantener la producción en los límites de lo sostenible. Deforestar el Amazonia para producir libros tipo El código Da Vinci o discos como los de operación triunfo o Britney Spears es un comportamiento completamente estúpido. El consumo compulsivo nos incita a consumir más, aun si lo que consumimos es únicamente basura.
Sin embargo los optimistas olvidan dos factores:
1) que el crecimiento de la población, se ha acelerado de tal manera en los últimos siglos que ha pasado de ser lineal a exponencial.
2) que la gente demanda, en todas partes, cada vez más bienes de consumo.
Como la población sigue creciendo, y como el número de objetos de consumo que tiende a desear cada persona es virtualmente infinito, no hace falta ser un genio para darse cuenta de que caminamos hacia la catástrofe.
Yo creo que hay dos posibilidades:
a) que acabemos comiéndonos a los humanos
b) un gobierno mundial que controle la natalidad y se encargue de que se produzcan las cosas verdaderamente necesarias, en vez de anegarnos en un mar de mierda (con perdón).
Mucha gente objetará que el gobierno mundial es algo utópico. Bien, puede ser. Pero alguien como Bertrand Russell (que no puede ser reputado de imbécil) proponía el gobierno mundial para salvarnos de la guerra nuclear. Hoy, con la crisis ecológica, un gobierno mundial sería aún más necesario.
Lo cierto es que gran parte de las cosas que se consumen son basura. Había una serie británica de los años 70, "Caída y auge de Reginald Perrin" en que un tío se hacía rico vendiendo basura.
Libros como la "Teoría de la clase ociosa" de Veblen o "La sociedad opulenta" de Galbraith sostienen que el capitalismo se dedica a producir un montón de bienes, muchos de los cuales son inútiles, pero sirven para demostrar el status superior de quien los consume.
Si no hay un goierno mundial, al menos debería haber un acuetdo mundial para controlar la natalidad y la producción
Hay quien cree que a mayor población, mayor número de productores,y por tanto mayor prosperidad.
Bien. Eso sería cierto si los recursos o materias primas fueran infinitos.
Lo curioso es que la mayoría de economistas razonan como si los recursos fueran inagotables.
Cuando alguien (como Galbraith) discrepa de la opinión general, lo tachan de hereje, y ni siquiera lo consideran economista.
La única forma de evitar el desastre es limitar la natalidad y mantener la producción en los límites de lo sostenible. Deforestar el Amazonia para producir libros tipo El código Da Vinci o discos como los de operación triunfo o Britney Spears es un comportamiento completamente estúpido. El consumo compulsivo nos incita a consumir más, aun si lo que consumimos es únicamente basura.
domingo, 20 de enero de 2008
Intuición matemática
Este blog no pretende exponer descubrimientos ni novedades en las matemáticas. He de reconocer que sólo he cursado unas pocas asignaturas de matemáticas en la universidad, principalmente de lógica y álgebra. A diferencia de Poincaré o Penrose yo no puedo explicar cómo se hacen descubrimientos en matemáticas, porque yo no he hecho ninguno. Sin embargo, contaré algunas experiencias psicológicas de mis pequeños aciertos en mate, aunque sea descubrir mediterráneos.
Un día, estudiábamos la aplicación que iba de un vector de tres números a uno de dos: de (a, b, c) a (a, b),. La profesora preguntó si ésta función tenía inversa. Yo al principio dije “Sí”. pero la profesora dijo: “¿Estás seguro?”. Yo lo pensé mejor y dije: “No, no . Porque cada imagen tiene más de una antiimagen (por ejemplo (1,2,1) y (1,2,2) tendrían como antiimagen (1,2).
Esta idea de dar la vuelta ala aplicación la hice, mentalmente, de una manera “espacial”, por decirlo así, ya que no escribí nada, sino que improbisé, cambiando de opinión en apenas unos segundos.
En ocasiones, aciertos de este tipo me han servido para constatar que no estaba perdido en clase (o que, si acaso, otros estaban mucho más perdidos que yo).
Otro acierto que me ayudó a coger confianza fue una vez que la profesora de Filosofía y Matemáticas preguntó qué cosa habíamos estudiado que era isomorfa a un álgebra booleana. Yo respondí que era la lógica proposicional, y resultó que estaba en lo cierto
Expondré otra ocasión en que descubrí un isomorfismo parecido. Esto ocurrió en los entrañables Foros del Rincón Matemático, un sitio de internet donde he encontrado gente con muy altos conocimientos de matemáticas (a los que agradezco que tengan además paciencia con mi ignorancia).En dicho foro , un usuario llamado Lau Luna propuso un rompecabezas:
“Un árbol binario completo parte de un nudo del que salen dos ramas; después cada una de estas se bifurca en un nuevo nudo, y así infinitamente. Del primer nudo parten dos ramas nuevas, de cada uno de los demás parte una sola rama nueva y continúa una rama antigua.
“El problema es que parece haber una demostración de que el conjunto de las ramas es no numerable y una demostración de que es numerable.
“PRIMERO. Cada rama contiene un número infinito de elecciones entre izquierda (I) y derecha (D), de manera que las ramas pueden biyectarse con las secuencias binarias infinitas del tipo (i,d,i,d,d,i,i,i...) Es claro que el conjunto de tales secuencias es no numerable, de hecho es biyectable con P(N), puesto que cada secuencia define un único conjunto de naturales y cada conjunto de naturales está definido por una única secuencia: supongamos que 'I' significa 'no está' y 'D' significa 'sí está'; entonces la secuencia que define al conjunto de los naturales mayores que 3 es (i,i,i,i,d,d,d,d,d...). En consecuencia, el conjunto de las ramas es no numerable.
SEGUNDO. Hay una forma sencilla de numerar las ramas: de izquierda a derecha y de arriba a abajo; para ver esto es útil dibujar una parte inicial del árbol, cosa que yo no puedo hacer aquí. Luego el conjunto de las ramas es numerable”.
"
Poco después a mí se me ocurrió un rompecabezas parecido. Aunque no terminaba de entender el problema planteado por Lau Luna, de algún modo lo “visualicé”, y propuse lo que me parecía un juego parecido: considerar los números reales entre 0 y 1, puestos en base binaria:
0'000
0,100
0,010
0,110
0,001
0,101
0,011
0,111
.......
¿No se podrían enumerar en este orden todos los números reales entre 0 y 1? Se podría objetar que no podemos llegar a conseguir un número irracional, puesto que tiene una expresión decimal infinita. Pero, según esta objeción, tampoco podríamos encontrar un conjunto infinito numerable simplemente con el método de incrementar en 1 cadanúmero natural a partir de 0.
Un moderador El Manco contestó lo siguiente:
“El ejemplo es excelente porque es exactamente el mismo que el de las ramas de LauLuna expresado de otra forma. Pero NO, en tu lista NO están TODOS los números reales ni mucho menos, sino SOLO los que tienen una expresión decimal finita en binario ("muy pocos")”.
De algún modo vago, mi intuición espacial había captado el juego de Lau Luna, y lo había transformado en un problema numérico. Creo que encontrar este tipo de isomorfismos es una característica fundamental de los descubrimientos matemáticos (si bien mis isomorfismos tienen un nivel de primaria en comparación con los que descubren los matemáticos).
Un día, estudiábamos la aplicación que iba de un vector de tres números a uno de dos: de (a, b, c) a (a, b),. La profesora preguntó si ésta función tenía inversa. Yo al principio dije “Sí”. pero la profesora dijo: “¿Estás seguro?”. Yo lo pensé mejor y dije: “No, no . Porque cada imagen tiene más de una antiimagen (por ejemplo (1,2,1) y (1,2,2) tendrían como antiimagen (1,2).
Esta idea de dar la vuelta ala aplicación la hice, mentalmente, de una manera “espacial”, por decirlo así, ya que no escribí nada, sino que improbisé, cambiando de opinión en apenas unos segundos.
En ocasiones, aciertos de este tipo me han servido para constatar que no estaba perdido en clase (o que, si acaso, otros estaban mucho más perdidos que yo).
Otro acierto que me ayudó a coger confianza fue una vez que la profesora de Filosofía y Matemáticas preguntó qué cosa habíamos estudiado que era isomorfa a un álgebra booleana. Yo respondí que era la lógica proposicional, y resultó que estaba en lo cierto
Expondré otra ocasión en que descubrí un isomorfismo parecido. Esto ocurrió en los entrañables Foros del Rincón Matemático, un sitio de internet donde he encontrado gente con muy altos conocimientos de matemáticas (a los que agradezco que tengan además paciencia con mi ignorancia).En dicho foro , un usuario llamado Lau Luna propuso un rompecabezas:
“Un árbol binario completo parte de un nudo del que salen dos ramas; después cada una de estas se bifurca en un nuevo nudo, y así infinitamente. Del primer nudo parten dos ramas nuevas, de cada uno de los demás parte una sola rama nueva y continúa una rama antigua.
“El problema es que parece haber una demostración de que el conjunto de las ramas es no numerable y una demostración de que es numerable.
“PRIMERO. Cada rama contiene un número infinito de elecciones entre izquierda (I) y derecha (D), de manera que las ramas pueden biyectarse con las secuencias binarias infinitas del tipo (i,d,i,d,d,i,i,i...) Es claro que el conjunto de tales secuencias es no numerable, de hecho es biyectable con P(N), puesto que cada secuencia define un único conjunto de naturales y cada conjunto de naturales está definido por una única secuencia: supongamos que 'I' significa 'no está' y 'D' significa 'sí está'; entonces la secuencia que define al conjunto de los naturales mayores que 3 es (i,i,i,i,d,d,d,d,d...). En consecuencia, el conjunto de las ramas es no numerable.
SEGUNDO. Hay una forma sencilla de numerar las ramas: de izquierda a derecha y de arriba a abajo; para ver esto es útil dibujar una parte inicial del árbol, cosa que yo no puedo hacer aquí. Luego el conjunto de las ramas es numerable”.
Poco después a mí se me ocurrió un rompecabezas parecido. Aunque no terminaba de entender el problema planteado por Lau Luna, de algún modo lo “visualicé”, y propuse lo que me parecía un juego parecido: considerar los números reales entre 0 y 1, puestos en base binaria:
0'000
0,100
0,010
0,110
0,001
0,101
0,011
0,111
.......
¿No se podrían enumerar en este orden todos los números reales entre 0 y 1? Se podría objetar que no podemos llegar a conseguir un número irracional, puesto que tiene una expresión decimal infinita. Pero, según esta objeción, tampoco podríamos encontrar un conjunto infinito numerable simplemente con el método de incrementar en 1 cadanúmero natural a partir de 0.
Un moderador El Manco contestó lo siguiente:
“El ejemplo es excelente porque es exactamente el mismo que el de las ramas de LauLuna expresado de otra forma. Pero NO, en tu lista NO están TODOS los números reales ni mucho menos, sino SOLO los que tienen una expresión decimal finita en binario ("muy pocos")”.
De algún modo vago, mi intuición espacial había captado el juego de Lau Luna, y lo había transformado en un problema numérico. Creo que encontrar este tipo de isomorfismos es una característica fundamental de los descubrimientos matemáticos (si bien mis isomorfismos tienen un nivel de primaria en comparación con los que descubren los matemáticos).
martes, 6 de noviembre de 2007
La máquina de componer música
Toda obra de arte es una combinación de elementos discretos. En el cuento de Borges “La Biblioteca de Babel” aparece la idea de una biblioteca de todos los libros posibles, bajo la forma de variaciones con repetición de todos los signos del alfabeto.
Todos los cuadros se pueden reducir a una colección de píxels coloreados, q ue puede codificarse mediante números enteros.
Igualmente, una obra musical puede reducirse a una curva continua, o a un conjunto discreto de unos y ceros codificados en un CD. Una vez, mi vana imaginación inventó la biblioteca de Bach que contenía todos los discos posibles.
En una entrada anterior me preguntaba si se podría hallar por azar en la biblioteca el Canon de Pachelbel. La respuesta es que no. Martin Gardner se pregunta si puede existior un algoritmo que discrimine cuales son las grandes composiciones.
En 1792 se publicó un libro atribuido a Mozart donde se mostraba un método de componer mediante tiradas de dados tantos valses como se quieran. El sistema permite componer 11^14 valses de inequívoco sabor mozartiano.
Con losd ordenadores actuales se puede escribir obras musicales en el estilo de Chopin, aunque probablemente no serán obra maestras. Paradójicamente, resulta más difícil comnponer una melodía popular con gancho. Como dice Martin Gardner "La música contemporámnea está tan llena “de aleatoriedad y disonancia que uno duda si repetir lo que dijera Mark Twain de la música de Wagner: es mejor de lo que suena."
Se han construido programas de ordenador que producen combinatoriamente textos de filosofía postmoderna carentes del menor sentido.
Todavía esperamos que un ordenador produzca algo que pueda competir con Yesterday o con Angie.
Todos los cuadros se pueden reducir a una colección de píxels coloreados, q ue puede codificarse mediante números enteros.
Igualmente, una obra musical puede reducirse a una curva continua, o a un conjunto discreto de unos y ceros codificados en un CD. Una vez, mi vana imaginación inventó la biblioteca de Bach que contenía todos los discos posibles.
En una entrada anterior me preguntaba si se podría hallar por azar en la biblioteca el Canon de Pachelbel. La respuesta es que no. Martin Gardner se pregunta si puede existior un algoritmo que discrimine cuales son las grandes composiciones.
En 1792 se publicó un libro atribuido a Mozart donde se mostraba un método de componer mediante tiradas de dados tantos valses como se quieran. El sistema permite componer 11^14 valses de inequívoco sabor mozartiano.
Con losd ordenadores actuales se puede escribir obras musicales en el estilo de Chopin, aunque probablemente no serán obra maestras. Paradójicamente, resulta más difícil comnponer una melodía popular con gancho. Como dice Martin Gardner "La música contemporámnea está tan llena “de aleatoriedad y disonancia que uno duda si repetir lo que dijera Mark Twain de la música de Wagner: es mejor de lo que suena."
Se han construido programas de ordenador que producen combinatoriamente textos de filosofía postmoderna carentes del menor sentido.
Todavía esperamos que un ordenador produzca algo que pueda competir con Yesterday o con Angie.
domingo, 8 de julio de 2007
Las máquinas de Turing y el infinito
Existen conjuntos de números que nunca podrán ser generados por una máquina de Turing. Por ejemplo, los subconjuntos de N. El conjunto Partes de N es no numerable mientras que el conjunto de funciones computables por máquina de Turing es, a lo sumo, numerable.
Existen funciones que nunca podremos calcular, por muy avanzados que sean los computadores que usemos.
Las funciones que pueden imaginarse son funciones de N a N. Ahora bien, imaginemos todas las funciones de N a {0,1}. Es evidente que son menos que las funciones de N a N.
Para cada subconjunto X de N hay una función característica:
f(n)=1 si n pertenece a X
f(n)=0 si n no pertenece a X.
Pero los subconjuntos de N forman un conjunto no numerable. Y el conjunto de las funciones computables por máquina de Turing es, a lo sumo numerable. Por tanto, existen funciones que no pueden ser computables.
Por último, existen números reales que nunca podremos generar mediante máquinas de Turing. Veamos, un número real como Pi es computable si existe una máquina de Turing tal que cuando el input es 0 genera la parte entera del número, cuando el input es 1 genera la primera cifra decimal del número, cuando el input es 2 genera la segunda cifra decimal del número, etc. Bien, pues como el número de máquinas de Turing es, a lo sumo, numerable, existen infinitos reales que no son computables.
Todas estas pruebas se basan en la teoría de los números transfinitos de Cantor. Uno de los problemas de la teoría de los números transfinitos es que no es falsable. Por ejemplo, nunca vamos a conseguir un número infinito numerable de máquinas de Turing. Por lo que nunca vamos a comprobar si las pruebas que usan números transfinitos son reales o son una fantasmagoría.
Existen funciones que nunca podremos calcular, por muy avanzados que sean los computadores que usemos.
Las funciones que pueden imaginarse son funciones de N a N. Ahora bien, imaginemos todas las funciones de N a {0,1}. Es evidente que son menos que las funciones de N a N.
Para cada subconjunto X de N hay una función característica:
f(n)=1 si n pertenece a X
f(n)=0 si n no pertenece a X.
Pero los subconjuntos de N forman un conjunto no numerable. Y el conjunto de las funciones computables por máquina de Turing es, a lo sumo numerable. Por tanto, existen funciones que no pueden ser computables.
Por último, existen números reales que nunca podremos generar mediante máquinas de Turing. Veamos, un número real como Pi es computable si existe una máquina de Turing tal que cuando el input es 0 genera la parte entera del número, cuando el input es 1 genera la primera cifra decimal del número, cuando el input es 2 genera la segunda cifra decimal del número, etc. Bien, pues como el número de máquinas de Turing es, a lo sumo, numerable, existen infinitos reales que no son computables.
Todas estas pruebas se basan en la teoría de los números transfinitos de Cantor. Uno de los problemas de la teoría de los números transfinitos es que no es falsable. Por ejemplo, nunca vamos a conseguir un número infinito numerable de máquinas de Turing. Por lo que nunca vamos a comprobar si las pruebas que usan números transfinitos son reales o son una fantasmagoría.
Suscribirse a:
Entradas (Atom)