El problema del censor

Interceptando series infinitas de caracteres.

DANIEL UZQUIANO

Inicio artículo

El siguiente problema se debe al matemático Andréi Kolmogórov, quien lo planteó a una audiencia de estudiantes de secundaria de la antigua Unión Soviética a principios de los años sesenta del siglo pasado. Tal como Dennis Shasha y Cathy Lazere describen el episodio, el problema de Kolmogórov nos pide que fijemos un repertorio de caracteres como el alfabeto de un lenguaje, y que definamos una palabra como una secuencia finita de caracteres de ese alfabeto. Ahora, supongamos que existe un repertorio de palabras prohibidas que un censor debe interceptar. Si una palabra no se encuentra entre las prohibidas, entonces es permisible. Kolmogórov planteó a su audiencia la siguiente pregunta: dada una secuencia infinita de caracteres del alfabeto que hemos fijado, ¿es posible dividirla en palabras de tal manera que todas ellas sean palabras prohibidas, o bien todas estén permitidas?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *