Angel "Java" Lopez en Blog

Publicado el 25 de Junio, 2012, 14:15

Hoy, leyendo la  Investigación y Ciencia Enero 2012, encuentro un artículo que describe y comenta un problema de Kolmogorov, dado a un grupo de estudiantes de "middle school", y rápidamente resuelto por un joven Leonid Levin. Sea:

- Un alfabeto finito (pongamos, letras, como a, b, c)
- Consideramos palabras a todo conjunto finito de esas letras. Ej: a, ab, aaab, cabaaaa, ....
- Hay un conjunto de palabras prohibidas (posiblemente infinito)
- Llamamos palabras permitidas a todas las palabras que no están en el conjunto de las prohibidas.

Demostrar que:

- Toda secuencia infinita se puede separarar en palabras todas prohibidas o todas permitadas, con la posible excepción de la primer palabra que puede no coincidir en tipo con el resto.

Eso es lo que demostró el entonces joven Levin.

Entiendo por secuencia infinita, una que tiene comienzo y no tiene fin (como los números naturales):

aaabbbccaababac.....

Es decir, NO ES INFINITA POR AMBOS LADOS:

.... aaaabbcbcbbaaa...

Tengo en mi biblioteca el libro Out of their minds: The lives and Discoveries of 15 Great Computer Scientists de Dennis Sasha y Cathy Lazare. Ahí debe estar este problema también. Pueden leer una versión más entendible que la mía en:

http://andysresearch.blogspot.com.ar/2006/12/feel-like-exercise-in-kind-of-infinite.html

Pongamos un ejemplo. Sea el alfabeto las letras a (letra a) y b (letra b). Sea las palabras prohibidas:

- a
- Toda palabra que contenga aa (dos a consecutivas)

Entonces la secuencia de ab repetida infinitamente:

abababababa....

puede descomponerse en TODAS PALABRAS permitidas ab:

ab ab ab ab ab ab

La secuencia infinita:

abbbbbbbbbbbbbb.... (todas bs)

se puede descomponer en:

a bbbb bbbb bbbb ....

donde sólo la primer palabra "desentona".

Pero vean que cualquier secuencia que contenga aaa (tres a) no puede evitar tener una palabra prohibida. Entonces, Levin tiene razón en este caso: basta con ver si la secuencia infinita tiene una cantidad finita o no de "aaa". Si tiene una secuencia finita, la primer palabra se toma compuesta por todas las letras iniciales HASTA llegar a la última aparición de "aaa" inclusive. El resto se puede partir en palabras todas permitidas. Si tiene una secuencia infinita de "aaa", se forman palabras que terminan, cada una de ellas, en una "aaa" correspondiente. Entonces, son todas prohibidas.

Pero el tema es demostrar que CUALQUIERA sea el criterio de palabras prohibidas, siempre se puede partir CUALQUIER secuencia en todas palabras prohibidas o todas palabras permitidas, excepto quizás la primera.

En el almuerzo estuve leyendo el artículo que mencioné al comienzo, y luego de meditar con carne al horno ;-)  tuve la idea de una demostración. Me parece que está bien, pero me queda la duda en un paso "al infinito". Por lo menos, tengo un algoritmo para ir separando una secuencia infinita en palabras (como las que pide la demostración) sin trabarme: es decir, voy procesando una secuencia finita cada vez más grande, y siempre tengo la posibilidad de ir haciendo la separación pedida. Bueno, les dejo la inquietud de demostrar el problema. En el próximo post publicaré mi (intento de?) solución y en otro post, la solución de Levin.

Adicional: muy bueno el artículo recordando a Kolmogorov: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.5016

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez