Hay algunas sutilezas o puntos difíciles que vamos a tener que pensar con respecto a entender aleatoriedad como incompresibilidad. Entonces, la primera no es una cuestión demasiado grave. Y es que, necesitamos una manera estándar de representar éstas compresiones. Digamos que la tarea que tenemos es la de comprimir una cadena determinada, o secuencia de símbolos, y vamos a escribir un programa de computador para eso, y queremos el programa de computador más corto posible. Me gusta la programación en Python Así que yo podría tratar de escribir un programa en Python y alguien más podría escribir un programa en C y alguien más podría hacerlo en C++ otro podría usar Lisp y quien sabe que harían otros. Pero todos estaríamos trabajando en diferentes lenguajes, y el algoritmo tendría diferentes representaciones en cada uno de estos. Así que necesitamos estar de acuerdo en algún tipo de estándar, o referencia, o método, o lenguaje para comparar estos algoritmos. lo que normalmente se hace aqui, para desarrollar formalmente estas ideas, es usar algo llamado la "máquina universal de Turing", entonces ésta máquina es un dispositivo que... puede hacer cualquier cosa, puede hacer cualquier cálculo. cálculos en tiempo, espacio discreto, o cálculos de estado discreto, discúlpenme. Um, y es capaz de emular cualquier otro computador, o dispositivo para hacer ese calculo. un computador que lo calcula todo, y que es el dispositivo estándar. un modelo de computador tan potente como ningún otro. En el desarrollo formal de estas ideas, que no hacen parte de éste curso, se trabaja en un marco dónde se comparan cosas en tipos de máquinas universales de Turing. Esta es una sutileza que tenemos que abordar. Y, bien, lo hemos hecho. Usaremos las máquinas universales de Turing La segunda sutileza es todavia más sutil y, ... más seria. y es que, ¿cómo sabemos si hemos encontrado el algoritmos mas corto posible, que pueda reproducir una secuencia? Tal vez una secuencia es comprensible, pero no he sido capaz de encontrarla, o no soy muy capaz, o no he tenido el tiempo suficiente. Esto podria ser el caso de Pi, que ciertamente parecía aleatorio. Y por cierto, de alguna manera, en algunas formas de verlo pi es realmente aleatorio. Todos los dígitos, si haces una expansión binaria, se vería, lo mismo que una moneda. Todas las posibles secuencias de ceros y secuencias de 1 ocurren con la misma frecuencia en la expansión binaria de Pi. Es bien raro, asi que Pi sería aleatorio. "algoritmicamente" o si usamos las maquinas universales de Turing el tipo de algoritmo esta bien. Pi no es aleatorio, pues hay un algoritmo para hacerlo. Bien, así que tal vez cada secuencia posible, de hecho, tiene algún algoritmo corto casi imposible de averiguar, para poder reproducirla, que no fuimos capaces de encontrarlo. Pero, podemos eliminar esa posibilidad. Les presento el argumento de la siguiente manera. Preguntemos si podemos encontrar algoritmos de compresión, formas de comprimir secuencias, que no parecen obvias. Una idea es, bueno, talvez hay un algoritmo que determina el algoritmo más corto. Un algoritmo para compresión que es siempre el óptimo. Así que este sería un algoritmo que escribe un algoritmo. O es como un programa que escribe un programa. Mas aún, éste programa escribiría el mejor programa automaticamente en el sentido de que sea el programa más corto. El único que comprima nuestra secuencia de símbolos tanto como sea posible. Esto sería una cosa asombrosa, pero se puede demostrar que un programa de este tipo no existe. No puedes escribir un programa que solo escriba el programa más corto. Así que esa idea, no la podemos, no podemos decir automáticamente, si hay un algoritmo más corto. Pero tal vez, hay un algoritmo más corto por ahí, incluso si no lo podemos encontrar. Y resulta que podemos eliminar esa posibilidad también. Y aquí está cómo se argumentaría esto. Primero pensemos en el conjunto de todos los algoritmos posibles, sobre todos los posibles esquemas para comprimir una secuencia de ceros y unos. Sería un conjunto infinito. Hay un número infinito de posibles algoritmos y que el programa sea infinitamente largo Allí tenemos este conjunto infinito, esta colección de todos esos algoritmos Pensemos sobre el conjunto de toda las secuencias posibles para comprimir. Este tambien seria un conjunto infinito. Estamos pensando de secuencias infinitas, todas las secuencias posibles de 0 y 1. Muchisimas! Tambien son infinitas. Así que tenemos dos conjuntos infinitos: de todos los algoritmos y todas las secuencias. Y si ambos conjuntos son del mismo tamaño, entonces puede suceder que cada algoritmo, perdon, que a cada secuencia le corresponde un algoritmo. Puede que no encontremos el algoritmo que corresponde a una secuencia, pero sabemos que el algoritmo puede existir. Sin embargo, sucede que no hay el mismo numero de algoritmo ya que hay secuencias. De hecho , hay un número infinito de más secuencias que algoritmos . Por lo tanto, hay certeza de algunas secuencias para las cuales no hay algoritmo que pueda comprimirla . Y vamos a llamar a esas secuencias azar Así que existe aleatoriedad en este argumento. Por otra parte , hay muchas más... secuencias que algoritmos, y si elijo una secuencia..... no quiero decir al azar si elijo una secuencia arbitraria, sumerjo mi mano en esta bolsa infinito de secuencias, Estoy casi seguro en el sentido de que con probabilidad una de esas secuencias será aleatoria. Será incompresible así que la idea técnica tal vez , algunos de ustedes están familiarizados con esto, es que el conjunto de todos los algoritmos es un infinito numerable y el conjunto de todos, secuencias infinitas de ceros y unos es incontable. Así que son muy diferentes infinitos.. conjuntos infinitos. Así que de nuevo , si elijo una secuencia de símbolos al azar, una secuencia de símbolos arbitraria puedo estar seguro con probabilidad uno que...., la... esa secuencia es aleatoria. Ahora vamos a volver a la ecuación logistica finalmente volver a los sistemas dinámicos . Así que si elijo una condición inicial, una condición inicial aleatoria una condición inicial arbitraria para la ecuación logística, que producirá una secuencia de ceros y unos. Y sé que vimos anteriormente , o argumenté anteriormente que la ecuación logística puede producir cada posible secuencia de ceros y unos, y todas las subsecuencias y se producen con igual probabilidad. Así que si elijo una.... una condición inicial una condición inicial arbitraria de la ecuación logística, con R = 4 Puedo estar casi seguro de que el resultado será aleatorio. Así, en este punto de vista, esta forma de pensar sobre la aleatoriedad, el proceso de producción de los símbolos definitivamente es determinante. Es una regla determinista inmutable pero el resultado es aleatorio. Que con probabilidad uno, Estoy absolutamente seguro que no hay ningún algoritmo que pueda que pueda comprimir la secuencia que produjo esa ecuación logística Así que la ecuación logística está produciendo aleatoriedad. O, ¿es? Esperen un minuto. La ecuación logística es en sí misma un algoritmo que está produciendo esta secuencia. Entonces, ¿cómo puedo decir que la ecuación logística está produciendo resultado aleatorio? porque hay un resultado aleatorio porque no hay algoritmo para.... para comprimir esa secuencia. ¿No es la ecuación logística , iteración ecuación logística por si misma sólo un algoritmo ? Así que, esta es una buena objeción, pero tenemos que pensar cuidadosamente acerca de la ecuación logística en el caos, y en particular la dependencia sensible de las condiciones iniciales Así que supongamos que usted me entregue una una secuencia aleatoria, sin un patrón obvio para ella, y tú dices, OK, mi tarea es averiguar si hay una manera de usar la ecuación logística para generar esta secuencia de ceros y unos Y al principio yo diría, Claro, por supuesto, tiene que haber. La ecuación logística produce posible secuencias de ceros y unos Así que esta secuencia que sólo me diste, no hay problema, puedo averiguarla O incluso si no puedo tal vez, hay muchas cosas diferentes para probar, condiciones iniciales para probar. Sé que la respuesta está ahí fuera, y entonces no habría un corto algoritmo. Así que sólo comprimí la secuencia que usted pensaba que era incompresible. Pero, espere un minuto La clave es que, con el fin de producir esa particular secuencia de símbolos, necesito especificar la condición inicial exactamente. Así que con toda la precisión necesito especificar la condición inicial Así que tengo que, en mi algoritmo, clasificar de la mecánica de la misma, es muy simple. Iterar con la ecuación logística R = 4,0 ese es un programa muy simple Muchos de ustedes han escrito sus propias versiones de esos programas. Las hojas de cálculo pueden hacerlo también. Pero entonces , a fin de que ese resultado, el que me dieron, puedo decir que lo he comprimido, y casi todas las condiciones iniciales, van a ser los números irracionales. Los números que siguen para siempre Y así, para que este algoritmo trabaje en reproducir esta secuencia de símbolos, necesito especificar la condición inicial, y necesito especificar la condición inicial exactamente. Y resulta que, por un argumento similar, casi todos los números entre cero y uno son aleatorios. Es una secuencia aleatoria de..... dígitos decimales seguida de un punto decimal. Y así, lo que necesito saber es el número exacto, esa condición inicial exacta, a un número infinito de decimales y la gran mayoría en el sentido de todo sino un conjunto de medida cero con probabilidad uno las condiciones iniciales son incompresibles He encontrado una especie de corto mecanismo para generarla pero necesito recordar una incompresible secuencia infinita de dígitos decimales con el fin de ejecutar el algoritmo y reproducir exactamente, la secuencia binaria, eso es lo deseado. Así que sí , la ecuación logística realmente está produciendo una salida aleatoria. Para resumir: la ecuación logística , un sistema dinámico determinista produce una salida aleatoria. La secuencia de ceros y unos, los símbolos de las dinámicas simbólicas de la ecuación logística son incompresibles. Y eso es lo que significa ser aleatorio. Es incompresible. Y se podría pensar, que la propia ecuación logística es una descripción comprimida de la secuencia sólo generada. Sin embargo, con el fin de reproducir esa secuencia, tenemos que especificar la condición inicial a una precisión infinita. Así que requiere recordar un número infinitamente largo Así que , es un programa corto pero necesitas darle un número infinitamente que de una descripción precisa, de la condición inicial Así la ecuación logística no es realmente una versión comprimida de la secuencia que produce. Espero que todo esto no haya sido demasiado confuso. Pero, para ser honesto, espero haya sido al menos un poco confuso. Pero en el buen sentido porque creo que lo que estos ejemplos hacen es enriquecer y complejizar nuestra noción de aleatoriedad Por lo tanto un sistema dinámico caótico al igual que las ecuaciones de Lorenz , o como la ecuación logística con R = 4, es determinista, pero es impredecible debido al efecto mariposa. Y es determinista , pero en realidad produce aleatoriedad en este sentido algorítmico de aleatoriedad. Así la aleatoriedad no tiene que ser un producto de la casualidad La aleatoriedad puede ser un producto del determinismo Y eso, creo, es una de las grandes lecciones del estudio del caos y los sistemas dinámicos Y voy a hablar un poco más sobre eso en el resumen de esta unidad y estos son temas que continuaremos revisando durante todo el curso .