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.
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.
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. 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
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.
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
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
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.
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.
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
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.
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.
Caracteríticas 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.
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.
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.
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.
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.
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.
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.
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.
Áreas de aplicación 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).
| Página siguiente |