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 .