El desarrollo formal de la teoría de la computación
se originó casi cincuenta años antes de que
apareciera el primer ordenador digital, el ENIAC (1945)
diseñado por John Eckert y John Mauchly (con objeto de
calcular trayectorias balísticas). Sus raíces se
encuentran en los trabajos de Hilbert, Gödel, Rosser,
Kleene, Church, Turing y Post, sobre la potencia del razonamiento
matemático con respecto a un problema computacional,
propuesto por el alemán David Hilbert, hace más de
90 años. Este problema, llamado el Problema de
Decisión (Entscheidungsproblem), se puede establecer de
una manera informal: 1.1 Breve historia de la Computación
(Gp:) Dada una representación formal de una
afirmación (enunciado) matemática, diseñar
un algoritmo (programa) que determine si la afirmación es
verdadera (teorema) o falsa (no válida
lógicamente). David Hilbert (1862-1943)
Si tal programa existe, cualquier conjetura se puede probar o
refutar expresándola formalmente y construyendo
mecánicamente una demostración, de manera que todo
el razonamiento matemático se basa en un fundamento
lógico, donde todos los enunciados (afirmaciones) ciertos
son demostrables (al igual que los falsos) y cada
afirmación es verdadera o falsa. Así cualquier
teoría matemática estaría formada por un
conjunto de axiomas y un conjunto de reglas de inferencia que
permiten generar enunciados válidos adicionales a partir
de enunciados válidos dados. La verdad de cada axioma se
admite a priori. Dicho programa se puede escribir si se puede
encontrar un conjunto de axiomas que: sean lo suficientemente
potentes para permitir que se pueda probar cualquier enunciado
verdadero, y que no admitan contradicciones, es decir, que una
afirmación y su negación no puedan ser ciertas al
mismo tiempo. 1.1 Breve historia de la Computación
En 1931, el matemático austriaco Kurt Gödel publica
su famoso teorema de incompletitud que establece que no puede
existir un conjunto de axiomas con las dos propiedades anteriores
y, por lo tanto, el programa anterior no se podrá
escribir. Más concretamente: 1.1 Breve historia de la
Computación (Gp:) "Ningún sistema de razonamiento
matemático es lo suficientemente potente para ser capaz de
probar toda afirmación cierta acerca de las propiedades de
los números naturales". Kart Gödel (1906-1978) La
Teoría de la Computabilidad se ocupa de construir un
formalismo matemático para razonar sobre la existencia o
no existencia de algoritmos efectivos para problemas
particulares. Los resultados que se prueben dentro de esta
teoría deben ser aplicables a todas las arquitecturas de
ordenadores, independientemente de sus parámetros, como
pueden ser la velocidad del procesador o el tamaño de la
memoria. Para ello tiene como base el concepto de modelo de
computación.
Necesitamos saber qué entendemos por algoritmo efectivo y
por problema. Aunque el desarrollo formal de la teoría de
la computabilidad se realiza en el siglo XX, sin embargo la
búsqueda de algoritmos efectivos para resolver ciertos
problemas se viene realizando desde hace más de 2000
años. Los matemáticos griegos, como se comprueba en
los trabajos de Euclides y Pitágoras, pusieron gran
énfasis en las técnicas constructivas. Así,
en geometría se plantearon algunos problemas que dejaron
sin resolver y que han constituido materia de
investigación durante mucho tiempo, como: El problema de
la cuadratura del circulo: "Dado un circulo, construir un
cuadrado con la misma área utilizando regla y
compás“ El problema de la trisección de un
ángulo: "Dividir un ángulo dado en tres partes
iguales mediante regla y un compás". El problema de la
duplicación del cubo: "Dado un cubo, construir otro con
exactamente el doble de volumen que el original, utilizando regla
y compás". 1.1 Breve historia de la
Computación
En este contexto, un algoritmo efectivo será aquel que
emplee en sus pasos de computación sólo regla y
compás. Sin embargo, hoy se sabe que ninguno de estos
problemas tiene solución. Por lo tanto, no existe un
método de construcción apropiado y así no
pueden existir tales algoritmos. La longitud de cualquier
segmento construido usando regla y compás se puede
escribir como una expresión en la que intervienen los
números naturales y las operaciones +, , y . La
duplicación del cubo es imposible pues se precisa
construir un segmento de longitud 21/3 (Descartes, 1637). La
trisección del ángulo requiere construir
líneas cuyas longitudes vienen dadas por las raíces
de un polinomio cúbico. Para ciertos ángulos, como
los de 60º estas longitudes no son expresables en la forma
requerida (Descartes, 1637). Lindemann probó en 1882 que
el número es trascendente y como cualquier solución
deberá construir un segmento de longitud , no existe un
algoritmo válido para su construcción. 1.1 Breve
historia de la Computación
En un programa de ordenador se genera una salida utilizando la
entrada leída. Así, cualquier programa se puede
considerar como un evaluador de una función, f, que aplica
algún dominio de valores de entrada, I, en algún
rango de valores de salida, O. La cuestión que surge ahora
es: ¿Qué problemas se pueden resolver con programas
de ordenador? Es decir, ¿Qué funciones se pueden
computar? Para establecer una formulación rigurosa de lo
que entendemos por algoritmo efectivo y por problema necesitamos
dar los siguientes conceptos: Un alfabeto es cualquier conjunto
finito no vacío; un símbolo (o letra) es un
elemento del alfabeto; una palabra es una secuencia o cadena
finita de símbolos de y la longitud de una palabra x de
*es el número de símbolos que la forman. 1.1 Breve
historia de la Computación
Dos palabras x e y de serán iguales si y sólo si
tienen todos los términos iguales; esto es, si y
sólo si tienen las mismas letras en las mismas posiciones.
El conjunto infinito de todas las palabras que se pueden formar
con símbolos de se representa por En el conjunto de las
palabras del alfabeto se define una operación llamada
concatenación de palabras de la manera siguiente: Dadas
las palabras x = a1 a2 …an e y = b1 b2 …bm, la
concatenación es la palabra xy = a1 a2 …an b1 b2…bm
Llamaremos lenguaje sobre un alfabeto a cualquier subconjunto L
de 1.1 Breve historia de la Computación
1.1 Breve historia de la Computación Cualquier orden entre
los símbolos de induce un orden entre las palabras de n de
la siguiente manera: 1. Para cada n, las palabras de longitud n
preceden a las palabras de longitud n+1. 2. Para las palabras de
igual longitud se establece el orden alfabético. A este
orden se le llama orden lexicográfico. Como consecuencia
de este orden podemos enumerar todas las palabras del lenguaje.
Es decir, cualquier lenguaje sobre es un conjunto numerable.
También podemos establecer funciones f : Un problema de
decisión es una función cuyo resultado es 0
ó 1 (falso o verdadero). Por lo tanto, todas las funciones
son problemas de decisión
1.1 Breve historia de la Computación Ejemplo: Problema de
decisión de la paridad de un número natural
expresado en base dos. El alfabeto es el conjunto {0,1} y cada
palabra corresponde a un número natural expresado en base
dos. En este caso f(x) vale 1 si x corresponde a un número
par, es decir, si la palabra x termina con el símbolo 0.
Así, f(010110) = 1 y f(11001) = 0. Dado cualquier problema
de decisión, el conjunto queda dividido en dos conjuntos
disjuntos: y que son el lenguaje correspondiente a f y su
lenguaje complementario
1.1 Breve historia de la Computación Ejemplo: El lenguaje
correspondiente al problema de decisión de la paridad es:
L(f) = {0, 00, 10, 000, 010, 100, 110,….} Hemos sustituido la
idea vaga de resolución del problema por el concepto
preciso de determinar si una palabra de entrada dada es un
elemento de un conjunto particular de palabras. Así,
determinar si un número natural escrito en binario es par
es equivalente a decidir si dicho número se encuentra en
el conjunto {0, 00, 10, 000, 010, 100, 110,….} Los modelos
formales de computación que vamos a estudiar nos
suministran un conjunto de operaciones básicas para
manipular los datos de entrada y obtener los datos de salida.
Así, en un modelo de computación cualquiera, un
algoritmo efectivo, para un problema de decisión dado, f,
es una secuencia de operaciones (permitidas) que determina si una
palabra cualquiera x está (o no) en L(f). Se dirá
que tal algoritmo (programa) reconoce el lenguaje L(f).
1.1 Breve historia de la Computación La Teoría de
la Computabilidad se ocupa de dividir el universo de todos los
lenguajes sobre , en aquellos lenguajes que pueden ser
reconocidos por algoritmos efectivos y los que no. Ello conduce a
las funciones no computables, es decir, a los problemas no
resolubles. Vamos a recordar algunos modelos clásicos
(máquinas) de computación, como las máquinas
de Turing (determinística y no determinísticas) y
los autómatas celulares que conducen a diferentes
formalizaciones del concepto de algoritmo, todas ellas
equivalentes (equivalentes también a otras formalizaciones
ideadas por Kleene, Church, Post, etc.). Esta equivalencia
refuerza la Tesis de Church-Turing que afirma: (Gp:) “la
clase de problemas que se pueden resolver utilizando el sistema
de programación de Turing es exactamente el mismo que los
que se pueden resolver utilizando cualquier sistema de
programación razonable”
La teoría clásica de la Computabilidad trata de
determinar qué problemas algorítmicos se pueden
resolver por ordenador en condiciones ideales de
disposición ilimitada de memoria y tiempo. Las
máquinas de Turing han sido aceptadas como modelos
estándar para el estudio de la computabilidad durante
más de medio siglo. Comenzaremos analizando el modelo
más simple de máquinas de estados finitos. Las
máquinas de estados finitos fueron introducidas
formalmente por Rabin y Scott (1959). Una máquina de
estados finitos consta de un dispositivo de memoria representado
por una colección finita de estados y de una
función de transición que actualiza el estado
actual como una función del estado previo y de la entrada
en curso. Se supone que toda la información viene
codificada por cadenas de símbolos (caracteres) de un
alfabeto fijo, que constituyen la entrada a la máquina.
Una formalización sencilla de una máquina de
estados finitos es el autómata finito. 1.2 De la
computabilidad clásica a las Redes Neuronales
Un autómata finito determinístico es una
quíntupla M = (K, ?, ?, s, F), K es un conjunto finito de
estados ? es un alfabeto s?K es el estado inicial F?K es el
conjunto de estados finales ? es una función de K?? en K,
llamada función de transición Un autómata
finito determinístico funciona de la siguiente manera: la
información que recibe la máquina viene codificada
en símbolos de un alfabeto que se escriben en una cinta de
entrada divida en cuadrados (en número ilimitado) y se
escribe un símbolo en cada cuadrado (casilla). La parte
principal de la máquina es una “caja negra”,
llamada unidad de control finita, que presenta, en cada momento
específico, un estado concreto del conjunto de estados
posibles K. La unidad de control finita puede leer el
símbolo escrito en la casilla correspondiente de la cinta
de entrada mediante una cabeza de lectura movible. Inicialmente,
la cabeza grabadora se coloca al comienzo de la cinta y la unidad
de control finito se encuentra en el estado inicial. 1.2 De la
computabilidad clásica a las Redes Neuronales (Gp:) ?
(Gp:) K ?
1.2 De la computabilidad clásica a las Redes Neuronales A
continuación el autómata lee el símbolo de
la primera casilla y la unidad de control finito pasa a un nuevo
estado que viene especificado por su función de
transición; el nuevo estado depende del estado previo y
del símbolo leído. Entonces la cabeza de lectura se
mueve una casilla a la derecha y lee el símbolo escrito en
dicha casilla. Este proceso se va repitiendo a intervalos
regulares, se lee un símbolo, la unidad de control finito
actualiza su estado y la cabeza de lectura pasa a la casilla
siguiente, así sucesivamente hasta que la cabeza de
lectura llega al final de la cadena de símbolo escritos en
la cinta de entrada. El autómata acepta (aprueba),o no
(desaprueba), la cadena de símbolos de entrada (palabra)
según que el estado que presenta la unidad de control
finito sea, o no, un estado del conjunto final de estados F. El
conjunto de palabras (cadenas de símbolos) que acepta un
autómata finito determinístico constituye el
lenguaje aceptado por la máquina. Ahora surge la siguiente
cuestión: ¿qué propiedades tienen los
lenguajes aceptados por un autómata finito determinista?
Se puede demostrar que son cerrados bajos las siguientes
operaciones unión, intersección,
complementación, concatenación y la
operación clausura (estrella de Kleene). Por lo tanto, son
los lenguajes regulares.
1.2 De la computabilidad clásica a las Redes Neuronales
Una posible generalización de los autómatas finitos
determinísticos es sustituir la función de
transición ? por una relación de transición
? que es un subconjunto finito de ???*??, donde ?* es el conjunto
de todas las cadenas finitas que se pueden formar con
símbolos del alfabeto ?, incluyendo la cadena
vacía. Es decir, ahora se permiten varios estados
siguientes para un símbolo de entrada dado y un estado
previo de la unidad de control. A este tipo de máquinas se
le llama autómatas finitos no deterministas. Sin embargo,
estas maquinas son equivalentes a los autómatas finitos
determinísticos, es decir, aceptan los mismos lenguajes.
Además, para cada autómata finito no deterministico
se puede construir un autómata finito
determinístico equivalente. Sin embargo, los
autómatas finitos determinísticos no se pueden
considerar como modelos verdaderamente generales para el
diseño de computadores puesto que no son capaces de
reconocer lenguajes tan simples como L = { an bn cn : n?Z+ }. Por
ello, es necesario introducir nuevos mecanismos que puedan
reconocer estos lenguajes y lenguajes mucho más
complicados.
1.2 De la computabilidad clásica a las Redes Neuronales
Uno de estos dispositivos más potentes es la
máquina de Turing que fue ideada por Alan Turing
(1912-1954). La máquina de Turing consta de una unidad de
control finito, de una cinta y de una cabeza grabadora que puede
usarse para leer o para escribir sobre la cinta. Una
máquina de Turing no determinística es una
cuádrupla M = (K, ?, ?, s), en la que K es un conjunto
finito de estados, que no contiene al estado de parada h. ? es un
alfabeto que contiene el símbolo blanco ?, pero no
contiene los símbolos L y R. s?K es el estado inicial ? es
una función de K?? en (K?{h})?(??{L,R}) , llamada
función de transición. Para estudiar si una
función es o no computable, utilizaremos la máquina
de Turing. Consideramos dos alfabetos ?o y ?1 y una f definida
de
1.2 De la computabilidad clásica a las Redes Neuronales
Una máquina de Turing, M = (K, ?, ?, s), se dice que
computa la función f si ?0, ?1 ? ? y para cualquier
entrada w? la máquina se para y en las celdas de salida
escribe la cadena de símbolos u, siendo f(w)=u. Si existe
una máquina de Turing que computa la función f se
dice que f es computable según Turing. Si ?0 es un
alfabeto que no contiene el símbolo blanco, ni los
símbolos fijos Y y N, entonces diremos que un lenguaje L?
es decidible según Turing si la función indicador
definida por la expresión: es computable según
Turing. También se dice que M decide L o que M es un
procedimiento de decisión para L.
1.2 De la computabilidad clásica a las Redes Neuronales
También una máquina de Turing se puede utilizar
como un aceptador de lenguajes. Si ?0 es un alfabeto que no
contiene el símbolo blanco, diremos que una maquina de
Turing M acepta una palabra w si M se para con dicha palabra.
Asimismo, diremos que M acepta el lenguaje L? si y sólo si
L = { w? : M acepta w } . Ahora surge la pregunta
¿cuál es la clase de las funciones computables
según Turing? la respuesta está clara, es la clase
de las funciones ?-recursivas. Una posible generalización
de la máquina de Turing es la máquina de Turing no
determinística, en la que se sustituye la función
de transición por una relación de transición
que asigna varios estados posibles a la unidad de control para un
mismo símbolo de entrada leído y un mismo estado
previo. Sin embargo, se demuestra que cualquier lenguaje aceptado
por una máquina de Turing no determinística es
aceptado también por una cierta máquina de Turing
deterministica.
¿Qué problemas (lenguajes) no resuelve (acepta) una
máquina de Turing? Si D es un diccionario infinito que da
respuesta a cada cuestión del tipo: ¿acepta (es
decir, consigue parar) la máquina de Turing M la entrada
w? No hay máquinas de Turing que decidan dicho lenguaje D.
A este problema se le conoce con el nombre de problema de la
parada para máquinas de Turing y consiste en determinar,
para una máquina de Turing arbitraria M y una entrada dada
w, si M parará alguna vez partiendo de dicha entrada.
También se han propuesto otras máquinas diferentes
a la de Turing, como las máquinas RAM (memorias de
registros direccionables), los algoritmos de Markov, los sistemas
de Post, las gramáticas formales de Chomsky, etc. Todas
ellas son equivalentes computacionalmente a la máquina de
Turing. Ello nos lleva a la tesis de Church-Turing: Cualquier
algoritmo se puede implementar en una máquina de Turing.
Sin embargo, a continuación vamos a ver que el problema de
la parada es resoluble neuronalmente. 1.2 De la computabilidad
clásica a las Redes Neuronales
Una red de autómatas consiste en un conjunto de elementos
de proceso, que van a ser máquinas de estados finitos,
localizados en los vértices de un digrafo (grafo
dirigido), uno en cada vértice. Cada elemento de proceso
recibe su entrada de las unidades vecinas y comunica su salida a
sus unidades vecinas. Formalmente, una red de autómatas es
un par A= constituido por un espacio celular C=(G,{Qi}), y una
familia de máquinas de estados finitos Mi (sólo un
número finito de ellas pueden ser distintas) con alfabeto
de entrada y función de transición local ?i : Qi??i
? Qi que aplica en , donde son los vértice conectados con
el vértice i. 1.2 Computación sobre grafos: Redes
de autómatas, autómatas celulares y RNA.
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Una red de autómatas
opera localmente de la siguiente manera: Una copia de una
máquina de estados finitos Mi, llamada elemento de
proceso, ocupa cada vértice i del grafo G, que es por ello
llamado célula o nodo. Cada copia Mi recibe como entrada
los estados que presentan las células vecinas y su propio
estado y entonces actualiza su estado según la
dinámica local establecida por su función de
transición ?i. La red repite esta actualización de
los estados de sus células repetidas veces. (Gp:) M1 (Gp:)
M1 (Gp:) M1 (Gp:) M1 (Gp:) M2 (Gp:) M3 (Gp:) M3
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Una red neuronal (discreta) es
una red de autómatas donde cada una de sus células
actualizan sus estados aplicando una función de
activación a una suma ponderada de las entradas (estados)
que recibe de las células vecinas. En una red neuronal,
cada arco (i,j) del dígrafo que conecta el vértice
i con el vértice j tiene asociado un peso wij, llamado
peso sináptico; la entrada neta de cada unidad celular
viene dada por una suma ponderada de los estados que presentan
las unidades celulares vecinas y así el nuevo estado de la
unidad celular i (potencial sináptico); la
actualización de los estados se realiza según una
función de activación fi ,fi : A ? A, que verifica
que fi(0)=0 (para evitar generación espontánea de
la activación), siendo A el conjunto de estados (niveles
de activación) que puede tomar las unidades
celulares.
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Formalmente, una red neuronal
(discreta) es un tripleta N = ?A,G,{fi}? constituida por un
conjunto A de estados posibles finito (valores de
activación), que admite una estructura
aditivo-multiplicativa (permite la suma de estados ponderados),
un dígrafo numerable G, pero localmente finito, y una
familia de funciones de activación, {fi}, una
función de activación para cada unidad celular. La
dinámica local de computación de la red viene dada
por la expresión: w12 w23 w31
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Un autómata celular es
una red de autómatas definida sobre un grafo regular con
una máquina de estados finita idéntica para cada
unidad celular. Generalmente, los autómatas celulares
están definidos sobre retículos (enrejados)
Euclídeos, de una o dos dimensiones que forman un grafo
homogéneo y sobre cuyos puntos enteros se colocan las
unidades celulares. Formalmente, un autómata celular es
una tripleta M=?C,N,M? constituida por un espacio celular C
=(?,Q) construido sobre un grafo de Cayley, ?, un conjunto finito
N de vértices de ?, una copia de una máquina de
estados finitos M en cada vértice i con alfabeto de
entrada Qd =Q?…?Q (d veces) y una función de
transición local
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Garzon y Franklin (1989)
demostraron que cada autómata celular es una red neuronal.
Además, demostraron que el problema de la parada de una
máquina de Turing es resoluble mediante una red neuronal.
Este resultado puede parecer un poco sorprendente y puede creerse
que constituye un contraejemplo para la tesis de Churh-Turing,
pero no es así, ya que dicha tesis se refiere a la
resolución algorítmica de problemas por medios
finitos, mientras que la red neuronal que se emplea en la
demostración requiere la utilización de un objeto
infinito (el dígrafo G). Sin embargo, aunque utiliza un
conjunto infinito de unidades celulares estás operan sobre
estados finitos. Asimismo, hay en la literatura varias
implementaciones diferentes de una máquina de Turing
mediante redes neuronales. Por otra parte, si nos limitamos a
redes neuronales acotadas, es decir, con un número finito
de unidades celulares y de valores de activación,
éstas se pueden modelar mediante un autómata finito
M, pensando en las configuraciones como el conjuntos de estados
del autómata finito. La función de
transición de M vendrá determinada por el
procedimiento de actualización de la red neuronal.
Así, las redes neuronales finitas son equivalentes
computacionalmente a los autómatas finitos.
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Sin embargo, una nueva forma de
computación está emergiendo basada en principios
completamente diferentes, que podemos llamar Computación
Celular. Este nuevo paradigma computacional suministra nuevas
formas de hacer la computación más eficiente (en
términos de velocidad, coste, disipación,
almacenamiento y calidad de la solución) para tratar
grandes problemas en dominios de aplicación
específicos. La computación celular se basa en tres
principios: Simplicidad Paralelismo inmenso Localidad La
arquitectura de von Neumann, que se basa en el principio de un
procesador complejo que realiza una tarea en cada momento, ha
dominado la tecnología de la computación en los
últimos 50 años.
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Computación Celular
Computación Distribuida Parcialmente conectadas paralelo
Local serie global Complejidad Simplicidad Arquitectura
Convencional Máquinas de Estados Finitos
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. La Computación Celular
viene también caracterizada por la conectividad local de
las unidades de proceso de manera que cada unidad de proceso
sólo se comunica con un reducido número de unidades
de proceso más o menos cercanas a ella. Además, las
líneas de conexión son portadoras de una
pequeña cantidad de información. El principio de
localidad conlleva que ninguna unidad de proceso tenga una
visión global del sistema; no hay un controlador central.
Computación Celular = Simplicidad + Paralelismo inmenso +
Localidad
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. La computación ADN, que
utiliza unidades moleculares (ADN) y esta inspirada en la
biología molecular. Aunque las unidades moleculares no son
demasiado simples pues pueden exhibir un comportamiento
biológico complejo, sin embargo, se pueden tratar como
elementos simples, desde un punto de vista computacional, al
poder realizar sólo unas cuantas operaciones
básicas en el tubo de ensayo. Para encontrar el camino
Hamiltoniano entre dos vértices dados (un camino que pasa
sólo una vez por cada vértice), Adleman (1994)
utilizó oligonucleótidos, es decir, cadenas cortas
de hasta 20 nucleótidos, para codificar los
vértices y la aristas de un grafo dado. A
continuación, colocó múltiples copias de los
oligonucleótidos en un tubo de ensayo; los
oligonucleótidos se enlazaban unos con otros formando
moléculas que representan caminos del grafo. Aplicó
entonces procedimientos de la biología molecular para
tamizar la plétora de soluciones moleculares ADN
candidatas. Es decir, encontrar si existe o no un camino
Hamiltoniano. El tamaño enormemente pequeño de
estas moléculas permite un paralelismo inmenso sobre una
escala completamente nueva. Además, serán
más rápidas, más eficientes
energéticamente y capaces de almacenar mucha más
información que los ordenadores actuales.
1.2 Computación sobre grafos: Redes de autómatas,
autómatas celulares y RNA. Las estructuras
autorreproductoras, que fueron estudiadas por von Neumann a
finales de los cuarenta. Chou y Reggia (1998) han usado bucles
reproductores para resolver el problema NP-completo de la
satisfacibilidad que consiste en ver si existe valores de verdad
que hacen verdadero un predicado (literal). Cada bucle representa
a una posible solución de factibilidad para el problema;
cuando se reproduce un bucle se obtiene un bucle hijo que
representa a una solución candidata diferente, que a su
vez se vuelve a reproducir. Bajo un forma de selección
artificial, las reproducciones que representa soluciones
prometedoras proliferan y las que no se eliminan.
1.3.1 Características de un sistema de Computación
Celular Tipos de células Las células toman una
valor de un conjunto de valores posibles, que puede ser discreto
(en cuyo caso el valor se llama estado) o continuo
(analógico). El comportamiento dinámico de la
célula viene determinado por una función de los
valores de sus células vecinas. Dicha función puede
venir dada por alguna de las siguientes formas: Una
enumeración exhaustiva, utilizada para células
discretas, donde el estado que debe presentar cada célula,
según la configuración de estados de la
células vecinas, viene recogido en una lista. Una
función parametrizada (lineal o no lineal) que describe el
estado siguiente de cada célula como una correspondencia
con los estados de las células vecinas. Un programa que
computa el estado siguiente de cada célula según
los estados de las células vecinas. Una regla de conducta
que especifica el comportamiento en diferentes situaciones. Dicha
regla puede estar inspirada en la biología molecular o en
la física cuántica.
1.3.1 Características de un sistema de Computación
Celular Movilidad Además de cambiar sus valores, las
células se puede cambiar también su
situación dentro de un ambiente dado y, por lo tanto,
pueden ser, o no, móviles. Conectividad La
comunicación entre células se realiza según
un esquema de conectividad específico. Así, las
células pueden estar colocadas sobre los vértices
de una rejilla regular con una geometría dada, como puede
ser rectangular, triangular, hexagonal, etc. En la rejilla
rectangular cada célula sólo tiene 4 vecinas. La
regularidad quiere decir que todas las células tienen que
tener el mismo esquema de conexión. Así, el esquema
de conectividad puede ser regular o irregular. Líneas de
conexión La conexión entre las unidades celulares
es simple, es decir, la información transmitida por ellas
es pequeña, generalmente sólo se transmiten los
valores de estado de las células vecinas.
1.3.1 Características de un sistema de Computación
Celular Topología celular El propio esquema de
conectividad induce una topología en las unidades
celulares. Sin embargo, en algunas formas de computación
celular las unidades celulares no están colocadas sobre
rejillas o grafos sino que están en un ambiente que
provoca contactos a causa del movimiento aleatorio o dirigido de
las mismas, como ocurre en la computación ADN, donde no
hay una topología rígida. Esto mismo ocurre
también en la computación basada en hormigas.
Dinámicas temporales El sistema se va actualizando
(cambiando, o no, de estados) con el tiempo, y cada
actualización se hace en cada instante o periodo de
tiempo. En una dinámica temporal sincronizada (paralela)
se actualizan todas las células al mismo tiempo
(simultáneamente) o un bloque específico de las
mismas, mientras que en la computación asíncrona
(secuencial) se actualiza sólo una célula cada vez,
siguiendo una cierta secuencia, que puede ser aleatoria. La
actualización se puede hacer a intervalos regulares de
tiempo, es decir, en términos de sucesos temporales
discretos, y la llamaremos actualización discreta. Si no
se hace ninguna división discreta del tiempo, la
actualización es instantánea, es decir,
continua.
1.3.1 Características de un sistema de Computación
Celular Uniformidad Se dice que el sistema es uniforme si todas
las células son del mismo tipo, es decir, son
idénticas y así ejecutan la misma función.
Hay sistemas celulares no uniformes, donde células
diferentes ejecutan funciones de transición diferentes. La
no uniformidad puede ser una ventaja computacional. Determinismo
frente al no determinismo El sistema es determinístico si
para una entrada dada el sistema siempre toma la misma
configuración de estados, y por tanto, termina con la
misma salida. En un sistema no determinístico para una
misma entrada podemos tener varias configuraciones de estados
posibles que conducirán, posiblemente, a salidas
diferentes. Según como sea la función de
transición de la célula, podemos tener un sistema
determinístico o no determinístico.
1.3.2 Comportamiento Programación La computación
celular requiere nueve técnicas de programación.
Distinguiremos dos tipos: Programación directa, donde el
programador especifica completamente el sistema en su conjunto de
salidas. Así, cuando el sistema recibe una entrada que es
un ejemplo o instancia del problema en consideración, el
sistema computa una salida correcta Métodos adaptativos,
donde el programador no puede especificar completamente todo el
conjunto de salidas, sino sólo parcialmente, y entonces
recurre a procesos de aprendizaje, evolución o
autoorganización para conseguir la funcionalidad deseada.
Así, métodos de aprendizaje y algoritmos evolutivos
se ha aplicado a las redes neuronales celulares para encontrar
los parámetros de la función de transición
con el fin de resolver algún problema dado. Los algoritmos
evolutivos se han aplicado a la computación ADN para
encontrar buenos códigos de secuencias de
nucleótidos.
1.3.2 Comportamiento Implementación Aunque la
mayoría de los experimentos en computación celular
se llevan a cabo en ordenadores convencionales, el objetivo
fundamental es la construcción de máquinas basadas
en unidades celulares para conseguir realmente la potencia de la
computación celular. En estas el coste se deberá
fundamentalmente a las conexiones y no a las unidades de proceso.
Hasta la fecha se ha desarrollado varias implementaciones, por
ejemplo: Implementación de autómatas celulares como
hardware digital de propósito general
Implementación de autómatas celulares usando
procesadores configurables Un chip analógico de redes
neuronales celulares Computación molecular en tubos de
prueba Autómata celular de puntos cuánticos donde
los estados no se codifican como voltajes, como con las
arquitecturas digitales convencionales, sino por la posiciones de
electrones individuales.
1.3.2 Comportamiento Escalabilidad La computación celular
permite una mayor escalabilidad que la computación
clásica debido a su conectividad local, a la ausencia de
un procesador central que tenga que comunicarse con cada
célula y a la propia simplicidad de las unidades
celulares. La adición de nuevas unidades celulares no es
ningún problema. Robustez La robustez de un sistema es su
capacidad para funcionar adecuadamente frente a fallos en alguna
de sus partes. Cuando una célula funciona incorrectamente
entonces los enlaces de comunicación fallan y nosotros
deseamos que el sistema continúe funcionando correctamente
o que la degradación sea aceptable. La conectividad local
favorece la contención de los fallos más
fácilmente al reducir los fallos a una región y
previene así la expansión al sistema, de manera que
una enorme cantidad de células permanecerán
operativas y funcionando correctamente.
1.3.2 Comportamiento Jerarquización La
descomposición jerárquica está presente en
las ciencias de la computación, a nivel de lenguajes de
programación, de códigos, de lenguajes
máquina y a nivel de transistores. Las jerarquías
aparecen en la naturaleza, de la molécula se pasa a la
célula y de la célula a un organismo, así
como las jerarquías de procesamiento en el sistema visual,
que comienza con el registro de la imagen en la retina (bajo
nivel) y termina con el reconocimiento de objetos (alto nivel).
Estas formas jerárquicas también aparecen en la
computación celular, bien fijadas en el conjunto de
salidas o emergen mediante la programación adaptativa.
Problemas locales frente a problemas globales Un problema local
contempla la computación de una propiedad en
términos puramente locales, como ocurre con el
funcionamiento de una unidad celular. Un problema global
contempla la computación de una propiedad general del
sistema. Así, un reto para el diseñador de modelos
celulares es encontrar reglas de interacción local para
resolver problemas globales.
1.3.3 ¿Para qué áreas de aplicación
es adecuada la computación celular? La computación
celular encuentra soluciones rápidas y eficientes para
problemas NP-completos que se presentan en diferentes dominios,
como en diseño de redes, teoría de grafos,
lógica, optimización combinatoria,
secuenciación, localización, búsqueda,
determinación de rutas óptimas, etc. Los modelos
celulares encuentran una aplicación natural al
procesamiento de imágenes digitales, como consecuencia de
su arquitectura, pues al ser las imágenes matrices
bidimensionales podemos utilizar rejillas rectangulares y
representar cada píxel de la imagen mediante una unidad
celular, y diseñando la máquina para que haga
tareas propias del procesado de imágenes. También
se ha utilizado modelos celulares para generar números
aleatorios de alta calidad. La capacidad de la computación
celular para realizar operaciones aritméticas permite que
se puedan construir calculadoras rápidas a una escala
increíblemente pequeña (nanométrica).