Friday, April 01, 2011

La imposibilidad de probar la conjetura de Collatz (III)


Tradicionalmente la física se ha centrado sobre el estudio de fenómenos computacionalmente reducibles, los cuales admiten una descripción simple y global. En los sistemas físicos reales, sin embargo, la reducción computacional es más la excepción que la regla. Podemos considerar por ejemplo la turbulencia de un fluído como un caso de esta irreducción computacional. En los sistemas biológicos, la extensión de este fenómeno de la irreductibilidad puede ser mayor incluso.

De la irreducción computacional se deduce que hay preguntas que pueden hacerse sobre el comportamiento de un sistema, pero a las cuales no se les puede contestar en términos generales mediante un proceso matemático o computacionalmente finito. Tales cuestiones han de catalogarse como indecidibles.

La conclusión a todo esto es que no hay ningún proceso de cálculo de longitud fija que pueda determinar el resultado final de un autómata celular en la generación N. De hecho, se necesita hacer el proceso explícitamente, paso por paso, para llegar a la generación N y ver qué pasa en ese momento.

La posibilidad de cuestiones indecidibles en los modelos matemáticos de los sistemas físicos puede verse como una manifestación del teorema de Gödel sobre la indecibilidad en matemáticas, demostrado por el propio Kurt Gödel en 1931. El teorema establece básicamente que en todos los sistemas matemáticos, hasta en los más simples, caben proposiciones que no pueden probarse o refutarse con un  proceso matemático o lógico. La prueba de una proposición puede requerir de un número de pasos lógicos indefinidamente grande. En la práctica hemos visto muchos teoremas matemáticos simples para los cuales las únicas demostraciones conocidas son muy largas. En la teoría de números, por ejemplo, hay muchos casos en que el número más pequeño que poseé una propiedad especial dada es extremadamente grande; muchas veces este número sólo puede encontrarse tanteando de uno en uno.

Relación de los autómatas celulares con la conjetura de Collatz

 Consideremos un autómata celular unidimensional de longitud finita. Pensemos en una línea de celdas o sitios, en los cuales se pueden poner las células correspondientes. Tomemos cada uno de los enteros, del 0 al 9, como un tipo de célula. Así entonces,  en cada sitio del autómata podemos poner un valor correspondiente a uno de los diez posibles valores. La regla de evolución de dicho autómata (para las siguientes generaciones del mismo), puede ser expresada en términos de la conjetura de Collatz. Si el autómata es par, divídase entre dos. Si el autómata es impar, multiplíquese por tres y al producto súmele la unidad.

Lo anterior define la conjetura de Collatz como un autómata unidimensional con k = 9, esto es diez posibles valores (contamos desde el cero), para cada sitio. Aquí la regla de evolución de la siguiente generación se define con respecto a la última célula en la línea del autómata unidimensional.

Cabe señalar que sin embargo, todos las celdas pueden estar o no afectadas por la regla usada. Por ejemplo, si tenemos que el autómata tiene una configuración impar, habrá que multiplicar por tres cada valor del autómata y llevar el acarreo a la siguiente célula a la izquierda. Esto por sí mismo es indecidible. No podemos saber a priori hasta dónde lleva el acarreo de valores de la cifra anterior a la siguiente. Este punto me parece notable. Dicho en otras palabras, la regla de evolución puede ir de 0 hasta n-1. A esto le llamamos r. La r es irreductible computacionalmente en la evolución del autómata. Si se considera que un autómata con k = 9 es muy difícil de simular, considérese un autómata con k = 1, en donde cada entero del autómata que pretende simular la conjetura de Collatz está en su expresión en binario. Esto podría reducir la complejidad en la operación de división entre dos, pues en binario  es simplemente recorrer al autómata a la derecha. Aún así, no queda muy claro qué más pasos deben darse para evitar la simulación explícita.

Así entonces, si la r es irreductible computacionalmente, estamos frente a la indecidibilidad del fenómeno descrito, el cual sólo puede ser expresado en términos de la simulación explícita. En otras palabras, la conjetura de Collatz se ha transformado en averiguar si el autómata que la describe puede ser computacionalmente irreductible o no. Hay pues que analizar los hechos que se presentan en la simulación del fenómeno. En el caso del número 27, el comportamiento del autómata es caótico y para casos como las potencias de 2, el resultado es elemental y reductible computacionalmente de manera trivial. Esto quiere decir que para números (o líneas de autómatas con k = 9), de la form 2^n, se requieren n-1 pasos para llegar a 1. No obstante esto, para ciertos números ipares o pares distintos a potencias de dos, el problema parece ser indecidible.

En conclusión, la conjetura de Collatz puede representarse como un autómata celular unidimensional elemental, en donde aparentemente la regla de evolución del mismo no es reducible computacionalmente para ciertos casos y en consecuencia, el teorema de Gödel apoya la indecidibilidad de la conjetura, la cual solamente puede ser, en principio, simulada explícitamente. La consecuencia directa es que no puede existir una demostración algebraica o analítica del problema en cuestión. Esto implica que la conjetura de Collatz es indecidible y computacionalmente irreductible. Con esto en mente, y afirmado por el teorema de Gödel, la conjetura debe sr vewrdadera, es decir, todos los números tienen la propiedad de ser maravillosos. Si no fuese así, sería fácil dar un contraejemplo para demostrar que la conjetura es falsa, pero nadie a la fecha ha encontrado alguno.

Sé, desde luego, que la conclusión hallada, apoyada por el teorema de Gödel puede dar a muchas suspicacias y más de uno puede poner en tela de juicio mi conclusión. Sigo creyendo que la conclusión es correcta, a menos que alguien me dé argumentos para rechazarla. Espero comentarios.

Con esto termino la discusión al respecto de la conjetura de Collatz. He desarrollado un programa para simular explícitamente dicha conjetura y en un par de días estará disponible para quien quiera trabajar sobre la misma, haciendo el desarrollo de la simulación. Pueden pedírmelo a morsa@la-morsa.com y a vuelta de correo se los mandaré. 

Cabe señalar que estos artículos en mi blog están basados en mi tesis de licenciatura, en donde creo que la parte de la conjetura de Collatz es algo original y quisiera creer que es mi contribución a este tema de la indecidibilidad e irreductibilidad computacional. 


(*) Una concha de caracol real y su equivalente generado con un autómata celular.

9 comments:

Emmanuel Garces said...

Que interesante Manuel !

Si este fuera el caso, entonces la secuencia de Collatz sería un ejemplo de un sistema irreducible que en muchos casos exhibe comportamiento complejo, y que sin embargo no es universal, es decir, que no puede simular cualquier computadora. Puesto que si pudiera simular cualquiera computadora entonces el Halting problem estaría resuelto.

Morsa said...

Esto que mencionas, Emmanuel, no lo entiendo. ¿Nos explicas?

saludos

Emmanuel Garces said...

Lo que quiero decir es que si la conjetura de Collatz es verdadera entonces el mecanismo que genera la secuencia no serviría para simular cualquier otro sistema computacional asi como lo hacen otros que también exhiben comportamiento complejo e irreducible (El autómata celular elemental regla 110, por ejemplo)

Puesto se conoce que en general no se puede decidir si un sistema computacional llegará a cierto estado (Halting problem). En otras palabras, cuando uno corre un programa no siempre se sabe con certeza si este parará en algún momento.

Pero si la conjetura de Collatz es cierta, entonces siempre sabremos que este sistema llegará a un cierto estado (Llegará al valor 1)

Por lo tanto, la secuencia de Collatz no podría simular cualquier otro sistema computacional arbitrariamente y por lo tanto no sería un sistema universal.

Emilio said...

Buscando como hacer llegar a alguien mi prueba sobre la certeza de la cojetura de Collatz con el fin de contrastarla y, en su caso, hacerla pública, me encuentro con este artículo con cuyo título no puedo estar de acuerdo.
Existe al menos una estrategia de prueba, muy fácil de explicar y entender, que nos lleva a aseverar la certeza de la conjetura.

Morsa said...

Pues bien, Emilio, date vuelo y explícanos cómo es demostrable.

Si aquí no te alcanza el espacio, puedes escribirme a mi correo morsa@la-morsa.com y yo me encargo, si así quieres, de publicar lo que tengas que decir.

saludos

Emilio said...

Estoy resumiendo mis notas sobre la prueba de la Conjetura de Collatz en un documento word.
No creo que pueda incluirla en el blog, pero trataré de adelantaros los puntos clave esta próxima semana.
Saludos.

Morsa said...

Emilio,

pues espero con ansias tus conclusiones. Siempre es muy interesante ver lo que otros han encontrado.

muchos saludos

Emilio said...

No se sin con las fórmulas de microsoft que he utilizado y que se han convertido en images habrá problemas para incluir directamente aquí el resumen de mi demostración de la conjetura de Collatz, por eso prefiero enviarte al correonto un documento con dicho resumen y las claves fundamentales de la demostración.

Falta el análisis de las sucesiones, pero eso es "dos y dos son cuatro" aunque me ocupa casi 2 páginas, por lo que si en este resumen no hay errores que invaliden la conclusión. Puedo decir que la conjetura de Collatz es cierta.

Saludos.

Daniel Alejandro Escobar Celis said...

No estoy seguro que realmente no pueda existir una demostración para este teorema. Lo que si estoy seguro y en parte es lo que siento que demuestra las afirmaciones aquí expresadas es: exceptuando el caso de las potencias 2^n no se puede encontrar una formula explicita que permita conocer el número de pasos que se necesitan para llegar al 1. Tal vez se puedan crear métodos probabilisticos que den una idea del numero de pasos, pero no una formula exacta.

De todas formas en caso de existir alguna demostración del teorema de Collatz, no sera nada obvia ni fácil de conseguir. En lo que si estoy seguro es que se pueden crear conjeturas similares o mas bien basadas en la de Collatz que si se pueden demostrar (fórmula recursivas que terminen en 1 o en uno o mas números específicos). No puedo decir mas al respecto, porque es algo en lo que recientemente he comenzado a trabajar, solo tengo algunas notas sueltas y ahora es que me falta tela por cortar.