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.