{"id":982,"date":"2018-05-23T10:54:32","date_gmt":"2018-05-23T13:54:32","guid":{"rendered":"http:\/\/157.92.27.101\/?p=982"},"modified":"2022-03-29T10:40:26","modified_gmt":"2022-03-29T13:40:26","slug":"en-busqueda-del-azar","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/en-busqueda-del-azar\/","title":{"rendered":"En b\u00fasqueda del azar"},"content":{"rendered":"

Para abordar los fundamentos esenciales de los modelos de c\u00f3mputo, investigadores del Instituto de Ciencias de la Computaci\u00f3n (ICC) trabajan en diferentes problemas vinculados al azar y los aut\u00f3matas.<\/strong><\/em><\/p>\n

Desde sus inicios la Teor\u00eda de la Computaci\u00f3n considera distintos modelos de c\u00f3mputo. De este modo se consolidaron 3 modelos principales: los aut\u00f3matas finitos<\/strong> (que son las m\u00e1quinas de computar m\u00e1s sencillas), las m\u00e1quinas de Turing<\/strong> (las computadoras usuales de hoy en d\u00eda) y las computadoras cu\u00e1nticas<\/strong> (cuyo funcionamiento no es digital). Cada modelo de c\u00f3mputo determina qu\u00e9 problemas se pueden solucionar usando este tipo de dispositivo y qu\u00e9 problemas no. Tambi\u00e9n determina a qu\u00e9 velocidad m\u00e1xima y m\u00ednima pueden resolverse los problemas. \u00a0Y, m\u00e1s sorprendente a\u00fan, cada modelo de c\u00f3mputo determina una noci\u00f3n de aleatoriedad, o dicho de otro modo: \u201cazar\u201d.<\/span><\/p>\n

Para abordar estos temas que hacen a los fundamentos de la disciplina, investigadores del Instituto de Ciencias de la Computaci\u00f3n (ICC) trabajan en diferentes problemas vinculados al azar y los aut\u00f3matas.<\/span><\/p>\n

Pero antes de adentrarnos en este asunto, \u00bfqu\u00e9 se entiende por \u201cazar\u201d? Si se piensa el azar en secuencias de s\u00edmbolos, como 0 y 1, o letras del abecedario (a, b, c) o de cualquier alfabeto; una de esas secuencias resulta azarosa cuando no se la puede nombrar de forma m\u00e1s abreviada que la secuencia misma. \u201c<\/span>La \u00fanica manera de nombrar una secuencia azarosa es, esencialmente, expl\u00edcitamente. Sino, las secuencias azarosas tendr\u00edan una forma abreviada y una ley de formaci\u00f3n de la secuencia, responder\u00edan a un patr\u00f3n<\/span><\/i>\u201d, explica Ver\u00f3nica Becher<\/strong>, investigadora del ICC, doctora en ciencias de la computaci\u00f3n y profesora del DC.<\/span><\/p>\n

Ahora bien, \u00bfcu\u00e1nto se conoce hasta el momento sobre el azar? \u00a0Para responder esa pregunta debemos remontarnos al a\u00f1o 1909 cuando \u00c9mile Borel, matem\u00e1tico franc\u00e9s, fue quien primero propuso una definici\u00f3n elemental de azar para secuencias infinitas. Esta definici\u00f3n de azar elemental se denomina \u201cNormalidad\u201d. \u00a0Borel se dio cuenta de que en una secuencia azarosa todos los s\u00edmbolos deben tener las mismas chances de aparecer, sino la secuencia se volver\u00eda un tanto predecible. Por ejemplo, si consideramos los s\u00edmbolos 0 y 1, el 0 debe aparecer la mitad de las veces y el 1 tambi\u00e9n. Y por la misma raz\u00f3n, todo par de s\u00edmbolos deben tener la misma chance de aparecer, por lo que el 00, 01, 10, 11; cada uno debe aparecer un cuarto de las veces. Y as\u00ed siguiendo para bloques de tres s\u00edmbolos, cuatro s\u00edmbolos, etc.<\/span><\/p>\n

En 1933 David Champernowne, un estudiante de matem\u00e1tica en Cambridge y \u00a0compa\u00f1ero de Alan Turing, demostr\u00f3 que la secuencia 123456789101112131415161718192021222324252627282930<\/strong>\u2026que se consigue concatenando todos los n\u00fameros enteros positivos en orden natural es una secuencia Normal. \u00a0\u00a0S\u00ed, es Normal, pero \u00bfes azarosa? A nosotros nos resulta completamente predecible. Tan predecible, que se puede hacer un peque\u00f1\u00edsimo programa que compute esta secuencia infinita, arrojando un s\u00edmbolo tras otro. \u201c<\/span>Este es el nivel de azar m\u00e1s bajo que casi no amerita llamarse \u2018azar\u2019 para nosotros, que conocemos el orden natural. Tampoco amerita llamarse \u2018azar\u2019 para las computadoras modernas (m\u00e1quinas de Turing). \u00a0Sin embargo, para un aut\u00f3mata finito la secuencia de Champernowne es impredecible porque el aut\u00f3mata finito no puede darse cuenta cu\u00e1l es la ley de formaci\u00f3n. Podemos programar un aut\u00f3mata finito para que lea una secuencia, \u00a0un s\u00edmbolo tras otro, y se comporte de manera diferente si el 0 y el 1 no aparecen con la misma frecuencia, o si alg\u00fan bloque aparece m\u00e1s frecuentemente que otro. Pero ning\u00fan aut\u00f3mata finito puede considerar operaciones aritm\u00e9ticas como la \u00a0ley de formaci\u00f3n de \u2018sumar 1\u2019 que tiene la secuencia de Champernowne\u201d<\/span><\/i>, afirma Becher.<\/span><\/p>\n

Como se explic\u00f3 anteriormente, las m\u00e1quinas de Turing son m\u00e1s poderosas que los aut\u00f3matas finitos y por lo tanto pueden predecir muchas secuencias que los aut\u00f3matas finitos no pueden. Sin embargo, \u00a0las m\u00e1quinas de Turing no pueden predecirlo todo. Hay un sinn\u00famero de secuencias que son azarosas para las m\u00e1quinas de Turing. \u00bfY esas secuencias pueden ser predichas por alguna otra m\u00e1quina? El mismo \u00a0Alan Turing, padre de la computaci\u00f3n moderna, concibi\u00f3 un modelo de c\u00f3mputo m\u00e1s poderoso, que es el c\u00f3mputo con \u201cor\u00e1culos\u201d. \u201c<\/span>Este modelo de c\u00f3mputo considera c\u00f3mo actuar\u00eda una m\u00e1quina si tuviera infinita informaci\u00f3n adicional. El modelo abstracto de c\u00f3mputo con or\u00e1culos en la actualidad se corresponde con un fen\u00f3meno corriente, que es el c\u00f3mputo interactivo con el usuario, donde los datos que brinda el usuario son tomados por un programa y gu\u00edan el c\u00f3mputo. El usuario es el propio or\u00e1culo<\/span><\/i>\u201d, puntualiza Becher. Y acent\u00faa, \u201c<\/span>una m\u00e1quina de Turing con or\u00e1culo puede ser m\u00e1s poderosa que una sin or\u00e1culo, por lo que algunas de las secuencias que eran azarosas para una m\u00e1quina de Turing, se pueden volver predecibles\u201d.<\/span><\/i><\/p>\n

 <\/p>\n

L<\/span>as m\u00e1quinas de Turing son m\u00e1s poderosas que los aut\u00f3matas finitos y por lo tanto pueden predecir muchas secuencias que los aut\u00f3matas finitos no pueden. Sin embargo, \u00a0las m\u00e1quinas de Turing no pueden predecirlo todo. Hay un sinn\u00famero de secuencias que son azarosas para las m\u00e1quinas de Turing.<\/p>\n<\/blockquote>\n

 <\/p>\n

La investigadora del ICC est\u00e1 liderando un proyecto de investigaci\u00f3n en Aleatoriedad y M\u00e1quinas de Estado Finito (aut\u00f3matas). Uno de sus desaf\u00edos m\u00e1s importantes consiste en realizar programas para m\u00e1quinas de Turing que generen secuencias azarosas para aut\u00f3matas finitos (es decir, que generen secuencias \u00a0normales en el sentido de Borel) pero altamente impredecibles: “<\/span>Se necesita inventar un generador pseudoaleatorio \u00a0que arroje secuencias infinitas sin per\u00edodo. Los actuales generadores pseudoaleatorios tiene per\u00edodo\u201d<\/span><\/i>,<\/span> detalla \u00a0Becher.<\/span><\/p>\n

Con la tecnolog\u00eda actual, al activar un generador pseudoaleatorio (valga el ejemplo de las m\u00e1quinas electr\u00f3nicas de los casinos) se lo asocia a un per\u00edodo, tan largo como uno quiera. Pasado el per\u00edodo, la secuencia se repetir\u00e1 exactamemente igual. Es por ello que las aplicaciones de hoy en d\u00eda utilizan generadores pseudoaleatorios y se comprometen a tener un per\u00edodo m\u00e1ximo. \u201c<\/span>Esto entra en conflicto con la era de Internet, donde todos los programas est\u00e1n pensados para no detenerse, es decir, para no tener un momento de reseteo, porque la comunicaci\u00f3n es un continuo. Vale aclarar que lo que \u00a0llamo \u2018la era de Internet\u2019 es exactamente la concepci\u00f3n de c\u00f3mputo infinito propuesta por Turing. Y es con la que hoy se concibe el mundo en que vivimos, con c\u00f3mputo interactivo en tiempo real, con la idea de seguir para siempre\u201d<\/span><\/i>, sostiene la investigadora.<\/span><\/p>\n

\"\"En este contexto, si el c\u00f3mputo es infinito en tiempo, entonces \u00a0los generadores pseudoaleatorios sin per\u00edodo resultan una necesidad pr\u00e1ctica y no solamente un problema te\u00f3rico. \u00a0\u201c<\/span>El problema ya est\u00e1 instalado y ahora se buscan soluciones posibles. Este desaf\u00edo viene con una meta adicional, esencial para las aplicaciones modernas, y es que los generadores pseudoaleatorios deben computar muy \u00a0r\u00e1pido<\/span><\/i>\u201d, concluye Becher.\u00a0<\/span><\/p>\n

 <\/p>\n<\/div>

<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"

Para abordar los fundamentos esenciales de los modelos de c\u00f3mputo, investigadores del Instituto de Ciencias de la Computaci\u00f3n (ICC) trabajan en diferentes problemas vinculados al azar y los aut\u00f3matas.<\/p>\n","protected":false},"author":3,"featured_media":983,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71,12],"tags":[26,40,25,42],"class_list":["post-982","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-actualidad","category-noticias","tag-aleatoriedad","tag-automatas","tag-computo","tag-turing"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/982","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=982"}],"version-history":[{"count":9,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/982\/revisions"}],"predecessor-version":[{"id":2171,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/982\/revisions\/2171"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/983"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=982"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=982"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=982"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}