191.-La-máquina-en-el-Fantasma

La máquina en el fantasma

“Sumisión temblorosa a ritos, voluntad sostenida a gritos, voluntad de unas máquinas tenidas por/expresión más alta del amor en un tiempo mecánicamente acariciado”, dice Fogwill por ahí de las máquinas.

Por todos lados, máquinas. Apretás un botón en el ascensor, y te lleva a ese piso. Apretás un botón en la cafetera, y sale un espresso. Apretás un montón de botones y un cilindro de acero a 1200 °C se mueve a gran velocidad hacia el choque que lo convertirá en un tubo. Apretás =1+1<Enter> en tu Excel y aparece 2, y atrás de todo: máquinas. Mecanismos (mecánicos, electrónicos, o como sea que estén implementados) que toman un input (información, materia, energía, etc.) y lo convierten en un output (vos llegando a otro piso, el café que necesitabas para seguir leyendo esta nota, un tubo, el resultado de una suma). Máquinas. Veloces y, por sobre todo, previsibles: viene un input, sale un output. Siempre igual.

La idea de máquina es la que inspiró a Alan Turing a sistematizar el concepto de algoritmo, de programa, que no es otra cosa que una máquina de procesar datos. Toma un input, lo procesa según unas reglas establecidas, y nos da un resultado. Por ejemplo, hay una máquina de Turing de sumar: le das dos números, te contesta con la suma de esos dos. Pero Turing fue más allá: inventó una Máquina Universal, que toma como input la descripción de cualquier otra máquina de las de Turing y se comporta como se comportaría ésta si la hubiera construido (siguiendo con nuestro ejemplo, toma la descripción de la máquina de Turing de sumar y dos números, y te da la suma de esos dos números como respuesta). La máquina-camaleón, la abuela materna, paterna, antecesor común y Lucy de todas las computadoras que andan y andarán por ahí.

Si la suerte está echada, que se levante porque la vamos a necesitar

En la esquina de enfrente se alza un fantasma que no recorre sólo Europa: lo aleatorio, eso que fluctúa con el azar y se empeña en escapar de la definición de máquina. Sabemos cosas generales de ese fluir, podemos hacer previsiones sobre una población, pero no podemos decir exactamente qué va a suceder sabiendo lo que sucedió. La relación entre input y output la vemos per speculum in aenigmate. Computación, el Manifiesto, inglés, latín bíblico, todo en un párrafo, ¿qué más podés pedir por este módico precio? ¿Filosofía barata y zapatos de goma? Lo pedís, lo tenés: así como las máquinas describen un tipo de orden, los sistemas aleatorios describen un tipo de desorden. Parecen cosas opuestas, Kaos vs. Control, Variabilidad vs. Presión de Selección. Y, sin embargo, podemos construir algoritmos –o algo así, no sea que me tiren con Wikipedia por la cabeza– que computan a partir de números random. O sea, construir una máquina que se alimenta de aleatoriedad. Como crear orden a partir del caos (o casi, aclaro, antes de que una horda de físicos y teólogos me muela a palos por hereje). Bienvenidos al mundo de los algoritmos randomizados. No, zapatos no hay.

NdR: Obvio que lo tuvimos que googlear. Nosotros tampoco hablamos latín. Pero ¡queda tan bonito! Y capaz que de ahí viene el título de Black Mirror. <3

Blowin’ in the breathalyzer

Imaginemos al pobre Nicolás, con su changuito lleno de bebidas alcohólicas de alta graduación, en una esquina cualquiera de una ciudad dibujada sobre una hoja perfectamente cuadriculada.

Está apurado para llegar a su habitación y beberse el changuito entero. Sabe que va a tomar en el camino, pero no sabe qué camino debe tomar porque, bueno, digamos que el changuito no fue la primera parada del aditivado cognitivo. Lo único que recuerda es que su casa está en una esquina exactamente n cuadras al sur y n al este de su posición actual. ¿Puede hacer algo para llegar? Por supuesto que sí. Lo único que importa es tomar n calles al sur y n calles al este, en cualquier orden. Así que en cada esquina tira una moneda para doblar o seguir derecho (hasta que se le acaben las calles en una dirección, después sólo tiene que seguir en la otra dirección hasta llegar). ¿Cuántos caminos puede recorrer el hombre antes de que podamos decir que llegó a casa? La respuesta la puede calcular hasta un Nobel de Literatura (es el famoso triángulo de Pascal),  pero lo que importa acá es que estamos seguros de que llegará a casa, aunque no sabemos exactamente cuánto tardará: algunas cuadras son cuesta arriba o tienen baches, otras son cuesta abajo y se recorren más rápido. Esto no es menor porque, en este tipo de algoritmos, lo aleatorio es el tiempo que tardan en terminar.

El algoritmo es randomizado porque la decisión de cómo elegir el camino se toma al azar. Este tipo de algoritmo randomizado se llama Algoritmo de Las Vegas. Termina siempre, y siempre con la respuesta correcta, pero no sabemos cuánto va a tardar en terminar, ni qué camino tomará.

¿Por qué querríamos usar este algoritmo? Primero, porque es barato de implementar: sólo necesito una moneda y saber la distancia y la dirección a casa. Pero hay más: como las decisiones son todas aleatorias, es imposible predecir por dónde irá Nicolás cada noche. Aun si alimentamos todos los caminos que Nicolás recorrió en el pasado al sesudo algoritmo de inteligencia artificial, no va a acertar más a menudo que eligiendo al azar. Resulta que el azar es una buena forma de ganarle tal vez a la información y la inteligencia de los otros (si son mayores que las nuestras, claro). Por otra parte, si en vez de un Nicolás tuviéramos mil Nicolases (o millones de usuarios de Waze, o cientos de programas idénticos tratando de vender acciones idénticas en el mercado, ponele) la randomización garantiza que la congestión será mínima (minga: garantiza que la probabilidad de congestión será mínima).

Por supuesto, si Nicolás tomó aún más que de costumbre, podemos hacerlo todavía más simple. Con un par de restricciones, podemos permitirle que, en vez de avanzar siempre hasta casa, vague al azar, en cualquier dirección, siempre dentro de la cuadrícula, y se detenga recién cuando llegue a casa. Podemos garantizar que llegará con probabilidad 1 (aunque va a tardar muchísimo más: en general tiene que recorrer una cantidad de cuadras proporcional al cuadrado de la distancia de la que partió).

La princesa está triste

Pasemos −sin solución de continuidad− del pecaminoso desierto de Las Vegas al prístino palacio en el que la princesa Graciela Patricia se aburre soberanamente, como corresponde, mientras mira el mar azul que asoma tras una ventana discreta (Spoiler Alert: ya no sale a trepar paredes para robar valiosas joyas. Esos días quedaron atrás). Así que decide aprovechar sus noches reales para calcular el valor de π. Sí, no es muy divertido, pero ¿quién dijo que las princesas se divierten?

Toma del tesoro del palacio un cuadrado, al que llama K, de 2×2, y dibuja adentro del cuadrado  un círculo C de radio 1 (hay una sola manera de meter un círculo justo justo en un cuadrado)

TP 1: Tirarle cosas a un papel y dejar que el azar nos guíe hasta π. La X marca el lugar de nuestro primer dardo hipotético o fideo munición no hipotético.

Ahora empieza a tirar con los ojos cerrados dardos perfectos (de esos que tienen las princesas pero vos no) que siempre caen en K, pero al azar. Algunos de esos dardos caen en C, y otros no.

Ahora, la astuta princesa suma un punto por cada dardo que cayó en C, y cero por cada uno que cayó en K pero no en C. Si la princesa divide la suma de los aciertos en C por el total de dardos que tiró, o sea, calcula cuántos puntos promedio hizo por tiro, ¿cuánto creen que le dará? La probabilidad de caer en C viene a ser el cociente entre la superficie de C y la de K. La superficie de K es fácil, 2×2=4. La de C (recuerden la primaria, o créanle, después de todo es princesa) es π. Mágicamente (o no), si dividimos la superficie de C por K da π/4. Si tiramos n dardos sumamos 1 punto n * π/4  veces en promedio. O sea, que la suma nos va a dar cerca de n * π/4  . Si lo dividimos por n nos da aproximadamente π/4. Es decir, alcanza con multiplicar el promedio de puntos que hicimos por 4 para obtener un número bastante cercano a π.

¿Eh? ¿Acabamos de obtener una de las constantes fundamentales de la matemática tirando dardos? No del todo. Si no le pegamos nunca a C, nos va a dar que π vale 0. Si embocamos todos los tiros, nos va a dar que π vale 4. Pero si jugamos lo suficiente, y el juego es aleatorio –y medio que estamos corriendo el riesgo de intentarlo entre todos y ver qué da, o explotar en el intento–, la princesa va a obtener, por lo general, un valor muy cercano a π. Y puede acercarse a  todo lo que ella quiera: cuantos más dardos tire, más improbable es que el número le dé lejos de π.

Y acá quiero hacer un parate, porque todos podemos ser princesas y hacer una versión aproximada del experimento en casa. Dibujen un cuadrado, y adentro del cuadrado un círculo que toque en un único punto los cuatro lados (prueben, hay una sola manera, y el centro del círculo va a coincidir con el del cuadrado). Háganlo como quieran: una cosa genial es que el experimento no depende del tamaño del cuadrado, ni del del círculo, ni del de la princesa (al menos en teoría). Pongan el cuadrado paralelo al piso en una superficie plana. Préndanle una vela a San Cono.

A continuación voy a calcular el valor de π, porque me place.

Agarren, digamos, 100 fideos munición, o más, y tírenlos al cuadrado con los ojos cerrados. Cuenten cuántos cayeron adentro del cuadrado, y cuántos también adentro del círculo. Repitan 100 veces. O 1000. No va a dar perfecto (algunos fideos se van a ir afuera del cuadrado, capaz que no tiran demasiado al azar, o el cuadrado les quedó inclinado, o algo asi), pero el momento de verlos juntar los fideos va dejarles un recuerdo memorable a los amigos.

Si son desconfiados, antimonárquicos, o gente particularmente visual, no tienen que creer en estas palabras, ni en la de la princesa; pueden jugar ustedes mismos acá.

Esta pausa está insertada para que vuelvan de jugar a calcular π. Qué locura, ¿no?

La sugerencia del chef es que elijan múltiples puntos entre 1 y 1000 y tiren varias veces los dados. Todo esto sobre colchón de finas hierbas.

Este tipo de algoritmo, donde lo aleatorio no es el tiempo que se tarda sino el resultado, se llama Algoritmo de Montecarlo. Puede darnos un valor correcto, o no. Pero, usando algunas propiedades estadísticas, si lo corremos suficientes veces, nos podemos aproximar al valor verdadero tanto como queramos. Además, es posible analizar la distribución de sus errores y entender cuán bueno es el resultado que nos da. Por ejemplo, podemos calcular que, si querés estar 90% seguro de que le vas a errar a π por menos del 10%, con unos 1500 tiros te alcanza. Si querés estar 99% seguro, unos 3000 son suficientes. En cambio, si querés estar seguro 90% de que tu error va a ser menor al 0.1%, anda calentando la muñeca, porque vas a necesitar tirar unos 11 millones de dardos.

OK, todo esto sirve para llenar de emoción los atardeceres sosos de la princesa. ¿Sirve para algo más? Sí. Primero, porque acabamos de calcular π tirando cosas sobre un pedazo de papel. SUNALOCURA.

Entre muchos otros ejemplos, hay un problema importantísimo que podemos atacar de esta manera: el de verificar si un número es o no primo (un número natural es primo si tiene exactamente dos divisores: 1 y él mismo). Muchos algoritmos de criptografía (como RSA, que se usa para firmas y certificados digitales, y que está detrás del candadito ese que aparece en el browser y hace que se sientan más seguros cada vez que buscan fotos de gatos o cajas en internet) están basados en elegir números primos. Pero no números pequeños, sino números con muchísimos bits de longitud (cuantos más dígitos binarios, o bits, tenga el número, más difícil de crackear es la clave). Y cuantos más bits tiene un candidato a número primo, más costoso es chequear si es o no primo.

El mejor algoritmo determinístico (o sea, que siempre te da el resultado correcto, una máquina como la gente, digamos) que existe se llama AKS (en realidad se llama Agrawal–Kayal–Saxena primality test, pero nos conocemos desde Cemento), y para testear si un número de n bits es primo, tarda un tiempo que es proporcional a n^6 (n*n*n*n*n*n). No parece tanto, a menos que pienses que testear si un número de 4096 bits es primo o no tarda unos miles de veces más que testear si uno de 1024 bits lo es. Multiplicamos por 4 el número de bits, multiplicamos por miles el costo de testear. Sí, crecer es difícil. No, esto no es una telenovela.

[Nota al margen: qué quiere decir que un número tiene 4096 ó 1024 u otra cantidad cualquiera de bits? Es una referencia a cuántos dígitos binarios se necesitan para escribirlo, cuanta memoria ocupa en la computadora. Pero además, cuán grande es el número. Por ejemplo, un número de 4096 bits tiene más o menos el mismo rango que un número decimal de 1230 dígitos (un millón de números se pueden escribir con 6 dígitos decimales. Así que un número de 1200 dígitos decimales esta cerca de  un millon elevado a la doscientos y pico. Uno de 1024 bits, como uno de unos 310 dígitos decimales].

Ahí aparecen los algoritmos randomizados para salvar (¡tal vez!) el día. Porque hay un algoritmo (el de Miller-Rabin) que contesta si un número de n bits es o no primo en un tiempo que es proporcional a n^2 (n*n). Pasamos de n^6 a n^2. Mucho mejor, ¿no? Bueno, no, sí, tal vez, quién sabe. Pero, OBVIO que esa disminución del costo viene con algún temita, y pasa que si el algoritmo dice que el número no es primo, siempre tiene razón, PEEEEEEERO si dice que es primo, hay una probabilidad de ¼ (el 25%) de que se equivoque.

Esto es completamente inaceptable. Cierren ese algoritmo y devuelvanme mi dinero.

Pero la misma aleatoriedad nos tira un centro: como cada corrida del algoritmo de Miller-Rabin es independiente de las demás –toma decisiones al azar en forma independiente–, si corro el algoritmo dos veces, la chance de que se equivoque las dos es de (¼)^2 o 6.25%. Y si lo corro 10 veces, entonces la probabilidad de equivocarse en todas es (¼)^10 , algo así como 1 en un millón. Y si lo corro 20 veces, 1 en un millón de millones. Mejora, ¿no? Y como el costo de cada corrida es n^2, el costo de testear si un número de 4096 bits es primo con probabilidad de error de 1 en un millón de millones es miles de millones de millones de veces más barato que correr AKS. Podés estar bastante seguro por un costo mucho menor, aunque si queres estar absolutamente seguro, es más caro. Como la vida misma, pero con algoritmos. O sea, como la vida misma.

Nace el bit en este mundo
remanyao por el destino

Hay una cantidad enorme de resultados teóricos, y de implementaciones prácticas de algoritmos randomizados, que van desde decidir cómo rutear mensajes en redes hasta machine learning. Y es interesante notar que todo esto proviene de resultados de áreas abstractas de la matemática, de teoría de números, por ejemplo, o de análisis probabilístico de algoritmos. Qué cosa esto de que las ideas geniales y con enorme impacto práctico a veces vengan de lugares imprevisibles, ¿no? Punto para dejar de preguntar para qué sirve lo que hacen los científicos y darse cuenta de que muchas veces lo más valioso es que aún no sabemos para qué sirve.

Este es el punto donde me asalta la duda: ¿lo digo o no lo digo? Es que me da cosa confesarlo. OK, mentí un poco. Dije que iba a mostrar cómo hacer máquinas a partir de aleatoriedad, cómo generar orden a partir del desorden. Después mostré como transformar números aleatorios en valores que caracolean alrededor de π, rutas a casa, números probablemente primos, todo pisteando como un campeón, aparentemente. Pero hay un problema que tal vez alguno haya advertido: todos nuestros algoritmos funcionan usando números aleatorios para tomar sus decisiones, y esa aleatoriedad de algún lado tiene que salir. La pregunta es: ¿de dónde sale? Porque no es lo mismo tirarle fideos a una hoja y contar los que caen adentro y afuera que tratar de pedirle a una computadora que te escupa un número al azar, porque resulta que es totalmente imposible generar bits aleatorios en una computadora (John Von Neumann lo dijo mejor que nadie: “Cualquiera que considere métodos aritméticos para generar números aleatorios está, obviamente, en estado de pecado”. Y antes de que alguien pregunte, todas las computadoras son máquinas de Turing, y todas las máquinas de Turing son métodos aritméticos, pecadoras al parecer).

Acá es clave volver al principio y recordar algo que no vemos tanto como deberíamos: nuestras computadoras son máquinas determinísticas, lo que quiere decir que por definición y a un nivel recontra fundamental no pueden generar números aleatorios. Nos conformamos con generar números pseudo-aleatorios (el término “maomeno aleatorios” no tuvo aceptación en la comunidad matemático-computacional, lamentablemente) para alimentar a nuestros bellos algoritmos sedientos de desorden, y son tan generosos que en la práctica funcionan bien. Bien. Cinco para el peso. Pseudo aleatorio por aleatorio. Computadoras deterministas que arrojan fideos que caen de manera casi casi al azar en el guiso algorítmico, pero nunca tanto. Porque resulta que, computacionalmente, es posible crear orden a partir del caos pero no caos a partir del orden, en un último acto de ironía de un Universo donde la termodinámica se empeña en ir hacia el caos siempre siempre, salvo cuando uno más lo necesita.

 

Koestler, Arthur The Ghost in the Machine (1990 reprint ed.). Penguin Group. ISBN 0-14-019192-5.
Ryle, Gilbert “Descartes’ Myth”. The Concept of Mind (New Univer ed.), 1949. University of Chicago Press. ISBN 0-226-73296-7.
The Police, “Ghost in the Machine”, 1981, A&M
Fogwill, En los bosques de pinos de las máquinas, 1998
Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), pp 230–265. Accesible en https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Figgis, M., Leaving Las Vegas. United Artists Pictures, 1995.
Hitchcock, A. To Catch a Thief,1955.
Gutierrez, J.M., Zweig, P., Yo no quiero ser princesa, 2014, Editorial Sudamericana.
AKS primality test. En Wikipedia. Accesado el 1/Nov/2016 https://en.wikipedia.org/wiki/AKS_primality_test
Rabin, M. O. (1980), “Probabilistic algorithm for testing primality”, Journal of Number Theory, 12 (1). Accesible en  http://ac.els-cdn.com/0022314X80900840/1-s2.0-0022314X80900840-main.pdf?_tid=8bb992f0-a040-11e6-ba2d-00000aab0f27&acdnat=1478011156_0ab894bb51724faeed6e2aede0bbf566
Mitzenmacher, M. and Upfal, E., Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2005,Cambridge University Press
Valiant L, and Brebner, G: Universal Schemes for Parallel Communication. STOC 1981: 263-277
Kearns M. , and Valiant L. (1989). “Cryptographic limitations on learning Boolean formulae and finite automata”. Symposium on Theory of computing. ACM. 21: 433–444. doi:10.1145/73007.73049.
Upfal, E., Felperin, S. and, Snir M: Randomized Routing with Shorter Paths. IEEE Trans. Parallel Distrib. Syst. 7(4): 356-362 (1996)
Von Neumann, J. (1951). “Various techniques used in connection with random digits”. National Bureau of Standards Applied Mathematics Series. 12: 36–38.

 




Hay 48 comentarios

Añadir más
  1. Matute

    Cuando describis el círculo C dentro del cuadrado K para calcular π este debería de ser de radio 1, no diámetro 1, si no queda chico.

  2. Uno que anda por ahi

    Excelente la nota muchachos, un agregado, la horda de físicos y teólogos, no solo se dedica a apedrear herejes, tambien se las han ingeniado para generar numeros realmente random disponibles para una maquina de Turing, aunque estrictamente, no generados por una maquina de turing. Algunos ejemplos a continuacion.

    https://www.random.org/ genera numeros random a partir del ruido atmosférico

    http://makezine.com/projects/really-really-random-number-generator/ genera numeros aleatorios a partir del ruido electronico de un circuito simple

    y el mejor de todos,
    http://www.idquantique.com/random-number-generation/quantis-random-number-generator/

    genera numeros random a partir de fenomenos de óptica cuanticos

    • Sergio Felperin

      Gracias! Si la memoria no me falla, la propuesta de usar fenómenos físicos para generar números aleatorios ya estaba en el paper de Von Neumann que citamos en la bibliografía. Pero (gran pero) una vez que usas un mecanismo externo para generar números aleatorios, lo que tenés no es más una máquina de Turing (y es necesario entender qué ganás y qué perdés)

  3. Teiko

    “…computacionalmente, es posible crear orden a partir del caos pero no caos a partir del orden, en un último acto de ironía de un Universo donde la termodinámica se empeña en ir hacia el caos siempre siempre, salvo cuando uno más lo necesita.”

    Genial! (no habría que explicar lo de la entropía un toque, pa que la referencia la agarre un publico mas amplio?) Buen artículo..

    Esta parte:
    “La probabilidad de caer en C viene a ser el cociente entre la superficie de C y la de K. La superficie de K es fácil, 2×2=4. La de C (recuerden la primaria, o créanle, después de todo es princesa) es π. Mágicamente (o no), si dividimos la superficie de C por K da π/4. Si tiramos n dardos sumamos 1 punto n * π/4 veces en promedio. O sea, que la suma nos va a dar cerca de n * π/4 . Si lo dividimos por nos da aproximadamente π/4. Es decir, alcanza con multiplicar el promedio de puntos que hicimos por 4 para obtener un número bastante cercano a π.”

    No se entiende muy bien, quizás haya que aclarar que la superficie de un circulo está dada por π*r^2 y en un circulo de radio=1 eso da π. Además habría que rellenar la parte que creo que te olvidaste o no se que pasó: ” Si lo dividimos por [?? n?] nos da aproximadamente π/4″

    Saludos!

    • Sergio Felperin

      Gracias por tu comentario. No quisimos extendernos explicando cosas de geometria. No es muy necesario acordarse de por que las superficies son lo que son.
      Tu comentario sobre la entropia es correctisimo, pero requeriria otro articulo para explicarlo!

  4. Nico

    En donde puedo encontrar una explicación de como se generan los numero maomeno aleatorios en una maquina de Turing??

    Muy buena lectura.

  5. Toni

    Tenés que hacer un post hablando de lo GROSO que fue Von Neumann. (solo fue una petición, pero el tono en lo que lo dije indica cierta urgencia.

    • Sergio Felperin

      De acuerdo con que hay que escribir algo sobre Von Neumann. De hecho, en el otro articulo que escribi para El Gato tambien hable de el (en el contexto del modelo de toma de decisiones de Von Neumann-Morgenstern que fue desbancado por los experimentos de Kahnemann-Tverski). El tipo era un monstruo, pero no particularmente romantico, asi que es poco conocido fuera de los que se dedican a estas cosas.

      • Toni

        Tal cual, Johnny era un gordito superdotado que le gustaba la joda y manejar mal. Revolucionó varios campos pero tuvo una vida “meh” así que quien lo juna.

        • Sergio Felperin

          Si, ademas era violentamente militarista y anticomunista. Una figura poco romantica. Mejor hacer peliculas sobre Nash o Ramanujan o Turing (que en vez de centrarse en sus increibles logros cientificos se centran en la psicosis, o lo dificil de ser indio o gay en inglaterra). En las peliculas sobre ciencia la ciencia suele ser un decorado para otra cosa.

  6. Elijo la caja

    ¡Genial artículo! Un par de cosas: les faltaron algunas aperturas de signos de interrogación (nada grave en los tiempos que corren, pero el lingüista que llevo dentro no me permite dejarlo pasar). Una vez leí, hace mucho tiempo, por lo que el recuerdo puede estar algo borroso, que las primeras computadoras que generaban números “al azar” lo hacían tomando datos “del entorno”, es decir, por ejemplo, multiplicando la hora por 9 y dividiendo por la fecha, o cosas así. A partir de eso, se desarrollaron multitud de métodos para que una computadora determinista dé números “masomeno” aleatorios.

    • Sergio Felperin

      Tenes plena razon.Hay algunos problemitas de tipeo. Vamos a ir corrigiendolos (tengo un metodo genial, agarramos un caracter al azar, y si esta mal lo corregimos).

      • Sergio Felperin

        Me doy cuenta de que no respondi tu segundo punto. Es cierto, se usaron muchos metodos que toman datos del entorno para generar numeros aleatorios. Pero es muy dificil que a) se porten razonablemente bien b) tengan un ciclo largo (el ciclo de un generador pseudoaleatorio es la cantidad de numeros que puede generar antes de que empiecen a repetirse). Hay montones de algoritmos geniales para eso (en otro comentario puse un link a wikipedia donde hay una listade los mas usados).

  7. Enzo Tagliazucchi

    que tan cierto es que una computadora clasica no puede generar numeros verdaderamente aleatorios?
    por ejemplo, si la computadora se basa en la evolucion de un sistema fisico
    (clasico) lo suficientemente inestable (caotico) para generar un numero aleatorio, y entonces para reproducir ese numero habria que medir con precision arbitrariamente grande las condiciones iniciales de ese sistema fisico inestable, entonces no podemos decir que el numero es verdaderamente aleatorio? (el determinismo matematico dista mucho del determinismo fisico).

    saludos, buena nota

    • Sergio Felperin

      No podes decir al mismo tiempo “una computadora clasica” y “se basa en la evolucion de un sistema fisico”. Las computadoras clasicas son maquinas de Turing (con ciertas limitaciones, por ejemplo, la memoria es finita) implementadas sobre lo que se da en llama arquitectura de Von Neumann (y otra vez aparece Von Neumann!) No esta basada en la evolucion de ningun sistema fisico, clasico o de otro tipo. Si lo estuviera, entonces los resultados de los programas dependerian de como esta implementado el sistema fisico de marras, y el conjunto de lo computable dependeria de cada computadora. Siempre es posible conectar un sistema fisico como el que propones (alguien lo comento antes, y puse un link a algunos de esos sistemas en otro comentario anterior) a una computadora, y que lea numeros aleatorios de ahi. Pero ningun sistema basado en una maquina de Turing puede generar numeros al azar.

      • DR. STRANGELOVE

        Estimado Sergio,

        como a Enzo, su artículo me generó ciertas dudas. Si bien no soy un experto en teoría de la computabilidad, esta afirmación me parece que sintetiza algunas cuestiones que menciona que son un poco confusas:

        “Y antes de que alguien pregunte, todas las computadoras son máquinas de Turing, y todas las máquinas de Turing son métodos aritméticos, pecadoras al parecer”

        Una computadora (en el sentido de una máquina que uno puede percibir usando sus sentidos) es un objeto físico, una máquina de Turing es una entidad abstracta (o puramente conceptual, como Ud. la quiera llamar). Una interpretación caritativa de “las computadoras son máquinas de Turing” sería algo así como “una máquina de Turing puede servir como modelo del funcionamiento de una computadora”. Pero aún así, hay funciones que son Turing-computables que obviamente no pueden ni podrán ser computadas por una computadora física porque al ser una máquina de Turing en ente abstracto no está sujeto a las limitaciones físicas a las que sí está sujeta una computadora. Parece que aquí Ud. ha querido introducir el concepto de máquina de Turing para referirse a un proceso determinista, pero siguiendo el espíritu de la observación de Enzo no hay que confundir conceptos de distinto tipo lógico.

        También resulta poco entendible la noción de “método aritmético” que nunca es aclarada, ni por qué una máquina de Turing “son (sic) métodos aritméticos”. En cualquier caso, hay máquinas de Turing probabilísticas donde la transición entre estados no es determinista.

        En mi opinión, el uso liviano de conceptos que pertenecen a la teoría de la computabilidad para hablar del comportamiento de máquinas físicas oscurece más que aclara, salvo que se haga con sumo cuidado.

        • DR. STRANGELOVE

          Me permito una nueva intervención:

          “Las computadoras clasicas son maquinas de Turing (con ciertas limitaciones, por ejemplo, la memoria es finita) implementadas sobre lo que se da en llama arquitectura de Von Neumann (y otra vez aparece Von Neumann”

          Esto también es falso, se han fabricado y se fabrican computadoras que no implementan la así llamada “arquitectura de von Neumann”. Nuevamente, dicha arquitectura es un ente abstracto, modelo ideal o como lo quiera uno llamar de organizar los componentes de una computadora, no es una ley inexorable de la naturaleza que toda computadora deba cumplir.

        • Sergio Felperin

          “Una computadora (en el sentido de una máquina que uno puede percibir usando sus sentidos) es un objeto físico”
          Salgamos del infierno epistemologico de definir las cosas fisicas como cosas que se pueden percibir con los sentidos (porque a menos que redefinas “los sentidos” mucho estas diciendo que cosas como los rayos gamma no son cosas fisicas, o que las alucinaciones lo son). A menos que tu proposito sea usarla para apoyar una maceta, es irrelevante, para lo que estamos discutiendo, que la computadora sea un objeto fisico. Agarra un disco de tu computadora y escribilo todo, de principio a fin, con datos. Ahora agarra otro disco, identico de fabrica al primero, y repeti la operacion. Desde el punto de vista fisico, los discos son distintos (pequeñas diferencias en donde estan grabados los datos, que es lo que permite recuperarlos, en algunos casos, despues de que reescribis el disco). Desde el punto de vista computacional, son identicos (en el sentido de que cualquier programa que tome a uno de esos discos como input producira exactamente el mismo resultado que si tomara al otro como input).El unico proposito de esto es mostrar por que es contraproducentes para entender esto mirar la implementacion. Lo relevante para cada ciencia son las propiedades emergentes. No conozco ecologos que se refieran a los ecosistemas en terminos de fisica cuantica. No es que las leyes de la cuantica no operen: es que son irrelevantes.

          “hay funciones que son Turing-computables que obviamente no pueden ni podrán ser computadas por una computadora física”

          Totalmente cierto. Y por eso menciono las maquinas de Turing. Lo que estoy tratando de mostrar es que una computadora no puede generar numeros aleatorios. Por lo tanto, si toda funcion computable por una computadora es computable por una maquina de Turing, y una maquina de Turing no puede computar numeros aleatorios, entonces una computadora tampoco.

          “También resulta poco entendible la noción de “método aritmético” que nunca es aclarada, ni por qué una máquina de Turing “son (sic) métodos aritméticos”. En cualquier caso, hay máquinas de Turing probabilísticas donde la transición entre estados no es determinista.”

          Tenes razon. No explico que es un metodo aritmetico. No es la idea del articulo. Simplemente aclaro que las maquinas de Turing son metodos aritmeticos, para mostrar que estan incluidas en el comentario de Von Neumann que cito justo antes. Mencionas maquinas de Turing probabilisticas. Es un punto interesante:
          A. Tenes las maquinas de Turing no deterministicas.(es decir, que para un estado S y un input A, contienen dos reglas distintas de la forma S,A,Algo y S,A,Otro Algo. Cuando la maquina esta en el estado S y recibe A como input en la cinta, el proceso sigue por separado por ambos caminos, y toma el resultado que se alcance primero). Lamentablemente, las maquinas no deterministas de Turing computan el mismo conjunto de funciones que las deterministas (por lo tanto, dado que no podes generar numeros aleatorios en una maquina determinista de Turing tampoco podes hacerlo en una no deterministica)
          B. Tenes las maquinas de Turing probabilisticas, que son como una maquina de Turing, pero con una cinta adicional de bits random disponible para lectura. Ahi es claro que podes generar numeros aleatorios (basicamente, solo tenes que manipular los bits aleatorios que te dan en la cinta adicional). En el mundo fisico, es equivalente a tomar una computadora tradicional y enchufarla a una fuente verdadera aleatoriedad, como las mencionadas en comentarios anteriores. Si le pegamos una fuente de aleatoriedad a una maquina de Turing, entonces puede generar numeros aleatorios.

  8. Patricio

    ¡Gran artículo!
    Una pregunta: usando qubits en vez de bits (computación cuántica) ¿el problema persiste?

    PD: Aguante Cha Cha Cha.

      • Marcos Feole

        No! No persiste! (Venía justo a comentar esto y me encontré la pregunta).

        Una computadora cuántica usa hardware que se compone por elementos (qubits) que se encuentran en estados cuánticos de superposición (o sea, combinación de estados), y que cuando son perturbados o medidos toman uno de los estados clásicos posibles con aleatoriedad fundamental y pura (tan fundamental es la aleatoriedad que en principio no se debe a una falta de capacidad nuestra para conocer el resultado). Sólo hace falta preparar un qubit en el estado necesario, y medirlo para obtener tu probabilidad fundamental de cara o ceca. Esto hace además que una computadora cuántica no sea una máquina de Turing determinista, aunque todavía no se sabe si se trata de una máquina de Turing indeterminista, o algo en el medio.

        Además, y dicho sea de paso, la aleatoriedad cuántica, hasta donde sabemos, es la única aleatoriedad fundamental que existe en la naturaleza (todo lo demás es nuestra incapacidad de medir las variables que decidirían la cuestión, como en el caso de los dados).

        Además venía a decir que la nota me pareció bárbara!! Gracias!!!

      • Marcos Feole

        Me auto-corrijo un detalle porque me quedó la duda después de mandarlo. En vez de “máquina de Turing indeterminista” debería haber escrito: máquina de Turing no determinista (la cual tiene una definición bien precisa).
        Escrito correctamente sería:

        Las computadoras cuánticas no son máquinas de Turing deterministas (definitivamente), y no se sabe aún si son o no son máquinas de Turing no deterministas, o algo en el medio entre ambas. (Lo de “en el medio” es por la cantidad y complejidad de problemas que podrían resolver en tiempo polinomial).

  9. Facundo

    Muy buen artículo, y super claro. Peco de ignorante, pero cuando decís “es posible crear orden a partir del caos pero no caos a partir del orden”, recuerdo en el curso de ecología haber visto que a partir del modelo de crecimiento logístico era posible generar ciclos caóticos. Es decir, no sería un ejemplo de que a partir del orden (partiendo de un modelo determinista) es posible generar caos?

    • Sergio Felperin

      La verdad es que caos tiene un sentido vulgar (en que lo usamos aqui) y que equivale a desorden, y un sentido tecnico (un sistema caotico es un sistema que tiene muy alta sensibilidad a pequeñas variaciones en sus parametros). Me imagino que tu curso de ecologia se referia al segundo sentido.

    • Marcos Feole

      Claro, el tema es que ese tipo de caos no tiene implicita una aleatoriedad fundamental, simplemente una incapacidad nuestra de medir las variables con tanta precisión como para hacer predicciones útiles, como en el clima o la bolsa.

  10. Guillermo Alvarez

    Felpe, articulo ameno, felicitaciones! Tu evolucion, partiendo de nuestro limo primigenio de la ESLAI y llegando al divulgador actual, solo puede explicarse en terminos de algoritmos randomizados (-:

    Agrego: es posible disminuir la complejidad computacional de un algoritmo a cambio de aumentar la aleatoriedad de la que depende, y viceversa. (Los detalles son algo tecnicos y pueden verse manipulando (semi)martingalas Itô, relacionadas con las secuencias de numeros aleatorios idealmente provistas como input para la maquina de Turing.) Algunas versiones limite de este tradeoff estan probadas y otras son problemas abiertos, pero versiones intermedias mas practicas pueden entenderse a traves del concepto de *desrandomizacion*. En lugar de suponer que tengo un generador perfectamente aleatorio y correr el algoritmo una vez, uso multiples semillas para un generador pseudo-aleatorio decente que realmente tengo y corro el algoritmo una vez para cada semilla–por ej., Theta(n) veces en la construccion de Adleman. Despues tomo el output generado por la mayoria de esos experimentos.

    Gran abrazo,
    **GA

    • Sergio Felperin

      Guille, una doble alegria! La de estar en contacto con vos despues de tantos años, mas la de que un articulo de divulgacion te haya gustado, siendo el experto que sos.

      El tema de tradeoff entre propiededas del algoritmo (complejidad y otras) y aleatoriedad aparece tambien en uno de los motivos que tuve para escribir esto: descubrir que el mismo Valiant (que escribio el paper sobre ruteo aleatorio que tanto usabamos en la epoca de mi tesis de licenciatura con Bwana) es quien escribio el paper mostrando que un monton de clasificadores debiles (ligeramente mejores que tirar una moneda) e independientes entre si podian configurarse mediante un mecanismo de voto para armar un clasificador fuerte (y en esta linea vinieron despues cosas como RandomForest, que reduce el bias de la clasificacion usando sampling para evitar overfitting). Cuando vi esas dos cosas juntas me dio la impresion de que habia una cosa muy rica que contar. El resto salio solo. Gran abrazo.

      • Guillermo Alvarez

        Felpe, gracias por tu generosidad–en algoritmos soy solo un aficionado, lejos lejos de los expertos. Por otro lado me consta que vos no solo entendes estos temas al nivel presentado en tu articulo, sino a un nivel mas cabal y profundo que redunda en la calidad de esta presentacion y de tus respuestas a preguntas de lectores. No se me han borrado las conversaciones grupales en los omnibus ESLAILa Plata sobre resultados fundamentales de Tarski, Goedel y Hintikka, y sobre nuestras demostraciones donde no nos habia quedado otra (!) que usar el Axioma de Eleccion. Como siempre, para ense#ar algo a nivel 10 lo tenes que entender a nivel 30. Mas alla de sus fallas, la Escuela Superior Latino Americana de Informatica nos ense#o a identificar lo que realmente sabemos.

        No conocia la contribucion de Valiant a la genesis de boosting; el no parece haberse movido mas por los circulos de Machine Learning. Buen punto de fondo el que acabas de insinuar: el poder de la randomizacion no solo surge de usar bits explicitamente generados para ser tan impredecibles como se pueda, sino tambien de meterme por la primera puerta que vea–de elegir una alternativa viable aun sabiendo que existen otras, nada mas que porque es la primera que una serie complicada (anche quizas deterministica) de factores me pone adelante. El fantasma de la randomizacion se manifiesta de multiples formas, hay material para otros articulos maduro y esperando a ser cosechado. Siempre se aprende algo nuevo, y siempre Computer Science debe mas avances fundamentales a los hungaros. En cuanto al excelentisimo director Bwana, no sera tomado por hungaro; su trayectoria post-sanctasanctorum de Catalinas (como lo llamaste alguna vez, de manera no desprovista de ironia) fue un farrago de… “actividades” que no presento sorpresas para nadie que lo hubiera conocido en ese entonces.

        Felicitaciones de nuevo por tu articulo “Destacado” en EGylC, y espero que nos pongamos al dia cara a cara antes de mucho. Gran abrazo,
        **G

  11. Laura

    Como lega total en la materia, quería preguntar si, a pesar de su determinismo, las computadoras no pueden usar su frecuencia (baja, pero aleatoria) de errores como un input de aleatoriedad que no esta basado en aleatoriedades externas de otros sistemas físicos. Entiendo que para eso debe saber que se equivoco, y que eso se puede lograr con suficientes corridas de los mismos algoritmos, pero no estoy segura. Si asi fuera, se podria luego usar la frecuencia de error (a veces 1 vez cada 100, a veces cada 1003, a veces cada 10^6 corridas) como un input aleatorio intrínseco?

    • Sergio Felperin

      Laura, tu pregunta es muy inteligente. Desde el punto de vista teorico, si tuvieras una maquina de Turing con la caracteristica adicional de poder cometer errores, tendrias un modelo de funciones computables distinto (De hecho, en alguna parte que no puedo recordar, el gran Martin Davis usa esto como argumento contra la idea de que el cerebro pueda ser imitado por una computadora). No es un resultado nuevo, lo probo Turing.
      Lo que propones es posible. Pero tiene muchos problemas. El primero es establecer si la tasa de fallas de tu computadora (suponiendo que pudieras detectarla: si haces un programa para detectar si la computadora fallo, la computadora podria fallar mientras corre ese programa) es realmente aleatoria, o si tenes fallas sistematicas (tiende a fallar cuando sube la temperatura, la temperatura sube cuando usas mucho la cpu, podes hacer que use mucho la cpu pidiendole que corra el programa X, con lo que la aleatoriedad se te va medio al diablo). Tampoco sabes, en principio, si la distribucion de errores es constante en el tiempo (o si a medida de que la maquina envejece cambia el tiempo entre errores y la distribucion de los mismos, como sucede en las maquinas mecanicas).
      Hay maneras mas baratas y seguras de hacer lo mismo: enchufar una fuente fisica de aleatoriedad al sistema. O usar numeros pseudo-random, que andan bastante bien.


Publicar un nuevo comentario