Expansión-modificación.

El mecanismo de expansión-modificación opera sobre una cadena So = {0,1}+.
Sobre cada símbolo de la cadena So, se aplica la siguiente transformación T:

MODIFICACIÓN. Con una probabilidad p :
0 -> 1
1 -> 0

EXPANSIÓN. Con una probabilidad 1 - p:
0 -> 00
1 -> 11


EL siguiente programa toma como argumento la probabilidad p y el nombre del archivo que contiene a la cadena inicial. El resultado es una nueva cadena. EL programa está disponible en la liga:

expa_modi

Desde una consola, cambien los permisos:

chmod 755 expa_modi

Para correr el programa:

./expa_modi p cad_inicial

donde p toma cualquier valor entre 0.0 y 1.0

El archivo que contiene la cadena inicial puede ser cualquiera que guarden en formato de texto o puedne bajar el siguiente:

cadena_1

El resultado de aplicar la transformación a una cadena genera una nueva cadena que depende de p. Se puede aplicar esta transformación a la cadena obtenida en la transformación anterior:

./expa_modi p cadena_1 > cadena_2
./expa_modi p cadena_2 > cadena_3

y con el comando:

cat cadena_3

Esto es:
S1 = T(So)
S2 = T(S1)

Cabe preguntarse si:

1. cualquier cadena Sx con longitud mayor o igual a la longitud de la cadena inicial So es alcanzable desde So y aplicando T con valores del parámetro de control p que pueden variar entre aplicaciones. P.e, si So = 01, despuès de aplicar una vez T, se puede llegar a las siguientes cadenas:

10
000
111

pero no se puede llegar a las siguiente scadenas:

0
001
11
0110100010
etc.

Para intentar medir alguna regularidad en las cadenas que se producen con T, se puede medir el número de veces que después de un 0 sigue un 0 (N00), el número de veces que después de un 0 sigue un 1 (N01), después de un 1 un 0 (N10) y después de un 1 un 1 (N11). O pueden medir el índice de agregación propuesto por Germinal Cocho y Pedro Miramontes:

I = (N00 * N11 - N01 * N10) / (N1 * N0 )

donde N1 es el total de 1 en la cadena y N0 es el total de 0 en la cadena. Este índice està definido en [-1,1]. Entre màs cercano a 1 es significa que hay largas subcadenas de 1's seguidas por largas subcadenas de 0s. Entre más cercano a -1, significa que hay subcadenas pequeñas de 1's seguidas de 0's, es decir, estàn intercalados los símbolos.

¿Què significa que I sea cercano a 0?

Traten de ver como cambia I al aplicar T.

Saludos.