En el artículo pasado vimos que la simulación por computadora es el método más usado (casi diría, único), para investigar muchos sistemas físicos y biológicos. Sin embargo, habría que preguntarse si la simulación constituye el procedimiento más eficiente, o si hay una fórmula matemática que pudiera llevar más directamente a los resultados. Para acotar la discusión, hemos de ahondar más en la correspondencia entre los procesos físicos y los computacionales.
Sabemos que todo proceso físico puede describirse a través de un algoritmo y que por lo tanto, cualquier sistema físico puede representarse como un proceso computacional. Se ha de determinar hasta dónde llega la complejidad de éste último. En el caso de los autómatas celulares, la correspondencia del proceso físico y el proceso por computadora es clara. El autómata celular puede contemplarse a la luz de un modelo para un sistema físico, pero también puede considerarse un sistema computacional análogo a una computadora digital ordinaria. En un autómata celular, la secuencia de valores iniciales a las células puede interpretarse como un dato abstracto o como información simplemente, de forma muy parecida a la secuencia de dígitos binarios de una computadora digital. A lo largo de la evolución del autómata se procesa esta información; los valores de las células se modifican de acuerdo a una regla predeterminada. De forma similar, los dígitos almacenados se modifican según las reglas contenidas en la unidad aritmética del procesador de la computadora.
Por ello, la evolución de un autómata celular a partir de su configuración inicial se asimila a una computación que procesa la información contenida en la configuración. Para los autómatas que muestran un comportamiento simple, la computación es sencilla. Por ejemplo, podemos tratar de detectar secuencias de tres celdas consecutivas cuyo valor inicial sea igual a uno. Por otro lado, a la evolución de un autómata celular que muestra un comportamiento complejo, puede corresponder una computación asímismo compleja.
Mediante una simulación explícita de cada paso, podemos determinar el resultado de un número dado en la evolución del autómata celular. El problema estriba en saber si existe un método más eficaz. Dicho de otra manera, ¿existirá alguna forma de acortarle la simulación paso a paso, esto es, un algoritmo que dé el resultado de muchos pasos en la evolución del autómata sin necesidad de hacer cada paso explícitamente? Si fuese así, la computadora podría ejecutar este algoritmo y sería posible predecir la evolución de un autómata sin necesidad de simularlo explícitamente. Esto sería análogo a encontrar una fórmula que fuese expresada en función del paso del tiempo que se desee observar. El fundamento de esta operación consistiría en que la computadora pudiese llevar a cabo una computación más refinada que el propio autómata celular y alcanzar los mismos resultados pero con menos pasos. Tal atajo es sólo posible si la computadora logra realizar cálculos intrínsecamente más complicados que los involucrados en la evolución del autómata mismo.
Podemos así definir una clase de problemas, llamados problemas calculables, que son los que admiten una solución en un tiempo finito, siguiendo ciertos algoritmos determinados. Una computadora simple, digamos una máquina sumadora, puede resolver un subconjunto de estos problemas. Sin embargo, existen máquinas universales capaces de resolver cualquier problema calculable. Las computadoras digitales son máquinas de este tipo. las instrucciones que puede ejecutar el CPU son suficientes para servir de elementos a un programa que pueda incorporar cualquier algoritmo. Además de las computadoras digitales, cierto número de sistemas se han mostrado como factibles de una computación universal, entre otros, algunos sistemas de autómatas celulares. En este sentido, se ha comprobado la capacidad de computación universal de un autómata bidimensional con sólo dos valores, 0 y 1, en cada celda. Otros argumentos incluso inducen a pensar que varios autómatas celulares (de clase 4), son también máquinas universales. Los candidatos más simples tienen tres posibles valores para cada célula y reglas de evolución que toman en cuenta solamente las células más cercanas.
Así entonces, lo importante aquí es que los autómatas celulares son capaces de una computación universal e imitan el comportamiento de cualquier máquina calculable. Y dado que cualquier proceso físico puede representarse como un proceso computacional, pueden también imitar la acción de cualquier sistema físico posible.
Si hubiese un algoritmo capaz de seguir el comportamiento de los autómatas celulares con una celeridad mayor que la propia evolución de los autómatas celulares, permitiría acelerar cualquier computación. Puesto que esta conclusión lleva a una contradicción lógica, se deduce que no puede haber un atajo válido general para predecir la evolución de un autómata celular arbitrario. Los cálculos correspondientes a la evolución son irreductibles, esto es, el resultado puede obtenerse solamente mediante la simulación explícita de la evolución. De hecho, esta simulación directa constituye el mejor método para determinar el comportamiento del autómata celular. No hay manera pues de predecir su evolución. Sólo queda observar lo que pasa.
La realidad es que no se sabe cuán extendido se halla el fenómeno de la irreductibilidad computacional entre los autómatas celulares, ni entre los sistemas físicos en general. A pesar de lo cual, resulta claro que los elementos de un sistema no necesitan ser muy complicados para que la evolución global del mismo sea computacionalmente irreductible. Cabe mencionar que la irreductibilidad computacional se da casi siempre en sistemas caóticos o complejos. No se conocen fórmulas generales que describan el comportamiento global de estos fenómenos. Quizás no lleguen a encontrarse jamás fórmulas así. En tal caso, la simulación explícita es el único medio de investigación posible.
En el siguiente artículo (que espero sea el último de esta serie), se hablará de la relación de los autómatas celulares y la conjetura de Collatz.
Tidak ada komentar:
Posting Komentar