Modelo de computación conexionista inspirado en las redes de procesadores evolutivos y su aprendizaje

La informática teórica es una disciplina básica ya que la mayoría de los avances en informática se sustentan en un sólido resultado de esa materia. En los últimos a~nos debido tanto al incremento de la potencia de los ordenadores, como a la cercanía del límite físico en la miniaturización de los componentes electrónicos, resurge el interés por modelos formales de computación alternativos a la arquitectura clásica de von Neumann. Muchos de estos modelos se inspiran en la forma en la que la naturaleza resuelve eficientemente problemas muy complejos. La mayoría son computacionalmente completos e intrínsecamente paralelos. Por este motivo se les está llegando a considerar como nuevos paradigmas de computación (computación natural). Se dispone, por tanto, de un abanico de arquitecturas abstractas tan potentes como los computadores convencionales y, a veces, más eficientes: alguna de ellas mejora el rendimiento, al menos temporal, de problemas NPcompletos proporcionando costes no exponenciales. La representación formal de las redes de procesadores evolutivos requiere de construcciones, tanto independientes, como dependientes del contexto, dicho de otro modo, en general una representación formal completa de un NEP implica restricciones, tanto sintácticas, como semánticas, es decir, que muchas representaciones aparentemente (sintácticamente) correctas de casos particulares de estos dispositivos no tendrían sentido porque podrían no cumplir otras restricciones semánticas. La aplicación de evolución gramatical semántica a los NEPs pasa por la elección de un subconjunto de ellos entre los que buscar los que solucionen un problema concreto. En este trabajo se ha realizado un estudio sobre un modelo inspirado en la biología celular denominado redes de procesadores evolutivos [55, 53], esto es, redes cuyos nodos son procesadores muy simples capaces de realizar únicamente un tipo de mutación puntual (inserción, borrado o sustitución de un símbolo). Estos nodos están asociados con un filtro que está definido por alguna condición de contexto aleatorio o de pertenencia. Las redes están formadas a lo sumo de seis nodos y, teniendo los filtros definidos por una pertenencia a lenguajes regulares, son capaces de generar todos los lenguajes enumerables recursivos independientemente del grafo subyacente. Este resultado no es sorprendente ya que semejantes resultados han sido documentados en la literatura. Si se consideran redes con nodos y filtros definidos por contextos aleatorios {que parecen estar más cerca a las implementaciones biológicas{ entonces se pueden generar lenguajes más complejos como los lenguajes no independientes del contexto. Sin embargo, estos mecanismos tan simples son capaces de resolver problemas complejos en tiempo polinomial. Se ha presentado una solución lineal para un problema NP-completo, el problema de los 3-colores. Como primer aporte significativo se ha propuesto una nueva dinámica de las redes de procesadores evolutivos con un comportamiento no determinista y masivamente paralelo [55], y por tanto todo el trabajo de investigación en el área de la redes de procesadores se puede trasladar a las redes masivamente paralelas. Por ejemplo, las redes masivamente paralelas se pueden modificar de acuerdo a determinadas reglas para mover los filtros hacia las conexiones. Cada conexión se ve como un canal bidireccional de manera que los filtros de entrada y salida coinciden. A pesar de esto, estas redes son computacionalmente completas. Se pueden también implementar otro tipo de reglas para extender este modelo computacional. Se reemplazan las mutaciones puntuales asociadas a cada nodo por la operación de splicing. Este nuevo tipo de procesador se denomina procesador splicing. Este modelo computacional de Red de procesadores con splicing ANSP es semejante en cierto modo a los sistemas distribuidos en tubos de ensayo basados en splicing. Además, se ha definido un nuevo modelo [56] {Redes de procesadores evolutivos con filtros en las conexiones{ , en el cual los procesadores tan solo tienen reglas y los filtros se han trasladado a las conexiones. Dicho modelo es equivalente, bajo determinadas circunstancias, a las redes de procesadores evolutivos clásicas. Sin dichas restricciones el modelo propuesto es un superconjunto de los NEPs clásicos. La principal ventaja de mover los filtros a las conexiones radica en la simplicidad de la modelización. Otras aportaciones de este trabajo ha sido el dise~no de un simulador en Java [54, 52] para las redes de procesadores evolutivos propuestas en esta Tesis. Sobre el término "procesador evolutivo" empleado en esta Tesis, el proceso computacional descrito aquí no es exactamente un proceso evolutivo en el sentido Darwiniano. Pero las operaciones de reescritura que se han considerado pueden interpretarse como mutaciones y los procesos de filtrado se podrían ver como procesos de selección. Además, este trabajo no abarca la posible implementación biológica de estas redes, a pesar de ser de gran importancia. A lo largo de esta tesis se ha tomado como definición de la medida de complejidad para los ANSP, una que denotaremos como tama~no (considerando tama~no como el número de nodos del grafo subyacente). Se ha mostrado que cualquier lenguaje enumerable recursivo L puede ser aceptado por un ANSP en el cual el número de procesadores está linealmente acotado por la cardinalidad del alfabeto de la cinta de una máquina de Turing que reconoce dicho lenguaje L. Siguiendo el concepto de ANSP universales introducido por Manea [65], se ha demostrado que un ANSP con una estructura de grafo fija puede aceptar cualquier lenguaje enumerable recursivo. Un ANSP se puede considerar como un ente capaz de resolver problemas, además de tener otra propiedad relevante desde el punto de vista práctico: Se puede definir un ANSP universal como una subred, donde solo una cantidad limitada de parámetros es dependiente del lenguaje. La anterior característica se puede interpretar como un método para resolver cualquier problema NP en tiempo polinomial empleando un ANSP de tama~no constante, concretamente treinta y uno. Esto significa que la solución de cualquier problema NP es uniforme en el sentido de que la red, exceptuando la subred universal, se puede ver como un programa; adaptándolo a la instancia del problema a resolver, se escogerín los filtros y las reglas que no pertenecen a la subred universal. Un problema interesante desde nuestro punto de vista es el que hace referencia a como elegir el tama~no optimo de esta red.---ABSTRACT---This thesis deals with the recent research works in the area of Natural Computing {bio-inspired models{, more precisely Networks of Evolutionary Processors first developed by Victor Mitrana and they are based on P Systems whose father is Georghe Paun. In these models, they are a set of processors connected in an underlying undirected graph, such processors have an object multiset (strings) and a set of rules, named evolution rules, that transform objects inside processors[55, 53],. These objects can be sent/received using graph connections provided they accomplish constraints defined at input and output filters processors have. This symbolic model, non deterministic one (processors are not synchronized) and massive parallel one[55] (all rules can be applied in one computational step) has some important properties regarding solution of NP-problems in lineal time and of course, lineal resources. There are a great number of variants such as hybrid networks, splicing processors, etc. that provide the model a computational power equivalent to Turing machines. The origin of networks of evolutionary processors (NEP for short) is a basic architecture for parallel and distributed symbolic processing, related to the Connection Machine as well as the Logic Flow paradigm, which consists of several processors, each of them being placed in a node of a virtual complete graph, which are able to handle data associated with the respective node. All the nodes send simultaneously their data and the receiving nodes handle also simultaneously all the arriving messages, according to some strategies. In a series of papers one considers that each node may be viewed as a cell having genetic information encoded in DNA sequences which may evolve by local evolutionary events, that is point mutations. Each node is specialized just for one of these evolutionary operations. Furthermore, the data in each node is organized in the form of multisets of words (each word appears in an arbitrarily large number of copies), and all the copies are processed in parallel such that all the possible events that can take place do actually take place. Obviously, the computational process just described is not exactly an evolutionary process in the Darwinian sense. But the rewriting operations we have considered might be interpreted as mutations and the filtering process might be viewed as a selection process. Recombination is missing but it was asserted that evolutionary and functional relationships between genes can be captured by taking only local mutations into consideration. It is clear that filters associated with each node allow a strong control of the computation. Indeed, every node has an input and output filter; two nodes can exchange data if it passes the output filter of the sender and the input filter of the receiver. Moreover, if some data is sent out by some node and not able to enter any node, then it is lost. In this paper we simplify the ANSP model considered in by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that the input and output filters coincide. Clearly, the possibility of controlling the computation in such networks seems to be diminished. For instance, there is no possibility to loose data during the communication steps. In spite of this and of the fact that splicing is not a powerful operation (remember that splicing systems generates only regular languages) we prove here that these devices are computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of restricted splicing processors with filtered connections. We proposed a uniform linear time solution to SAT based on ANSPFCs with linearly bounded resources. This solution should be understood correctly: we do not solve SAT in linear time and space. Since any word and auxiliary word appears in an arbitrarily large number of copies, one can generate in linear time, by parallelism and communication, an exponential number of words each of them having an exponential number of copies. However, this does not seem to be a major drawback since by PCR (Polymerase Chain Reaction) one can generate an exponential number of identical DNA molecules in a linear number of reactions. It is worth mentioning that the ANSPFC constructed above remains unchanged for any instance with the same number of variables. Therefore, the solution is uniform in the sense that the network, excepting the input and output nodes, may be viewed as a program according to the number of variables, we choose the filters, the splicing words and the rules, then we assign all possible values to the variables, and compute the formula.We proved that ANSP are computationally complete. Do the ANSPFC remain still computationally complete? If this is not the case, what other problems can be eficiently solved by these ANSPFCs? Moreover, the complexity class NP is exactly the class of all languages decided by ANSP in polynomial time. Can NP be characterized in a similar way with ANSPFCs?

Arquifanía: la arquitectura como manifestación

Arquifanía: arquitectura y epifanía. La revelación que se da en el proyectar, en el construir y en el habitar. Desentrañar los protagonistas y el escenario de ese encuentro es el objetivo de esta tesis. Nace de una doble inquietud: la relación entre literatura y arquitectura y la constatación de algo inconmensurable en la arquitectura. A lo largo de los siglos la teoría de la arquitectura ha hecho un gran esfuerzo por racionalizar todos los aspectos de la disciplina. La sistematización del orden y jerarquía de los espacios, el uso de parámetros más rigurosos en los cálculos estructurales, el desarrollo de la técnica y el estudio de los esquemas funcionales han supuesto una fuente inagotable de manifestaciones arquitectónicas. Los paradigmas científicos, incluso, han resultado fundamentales en la creación de nuevos lenguajes. Sin embargo, en este camino de racionalización se han orillado aspectos de difícil cuantificación. Pese a que en la experiencia diaria del arquitecto se constata la presencia de parámetros inconmensurables, la teoría de la arquitectura no ha integrado de forma sistemática este conocimiento. De aquí nace la presente tesis doctoral. En ella se estudia, por analogía con el resto de artes, el concepto de manifestación. Se analiza de qué manera la obra arquitectónica se manifiesta, haciendo uso de su autonomía, y se convierte en la que dirige al arquitecto en todos los tiempos de la existencia de la obra: desde su génesis en el tiempo del proyecto hasta la experiencia de la obra terminada en el tiempo de la historia. Se considera que reflexionar en el concepto de manifestación puede aportar luces sobre la disciplina arquitectónica en un doble momento. Se estudia por una parte la actitud y el proceder del arquitecto ante la génesis del proyecto y por otra su posicionamiento ante la obra ya existente, sometida a su análisis (para la posterior síntesis) generando una espiral de conocimiento siempre abierta y en continuo enriquecimiento. Se analiza la obra de María Zambrano, filósofa, y José Ángel Valente, poeta, en busca de la definición del concepto de manifestación. El momento creativo, la naturaleza de la palabra poética, la actitud del poeta ante su obra, el conocimiento y la revelación de la belleza son temas recurrentes en sus obras y crean un corpus teórico que permite elaborar una teoría poética sólida y abierta, llena de sugerencias que se dirige con precisión al momento de la generación de la forma: su epifanía. A continuación se repasa el concepto de manifestación en la actividad de algunos artistas de la modernidad que, de manera implícita o explícita, han hablado del concepto de epifanía. A menudo de forma intuitiva, los artistas han detectado en su actividad la condición de ser depositarios de un don que se renueva en cada obra ejecutada. Entrelazado con su trabajo y con la disciplina diaria los artistas experimentan un diálogo con la obra, que se revela libre y con voluntad de manifestarse. Enunciado el problema y hecho el repaso por el mundo de la creación artística, nos enfrentamos con el núcleo de la tesis: ¿hasta qué punto y de qué manera el concepto de manifestación es válido en arquitectura? El discurso busca en la actividad de múltiples arquitectos la validez del concepto de manifestación. Se rastrean testimonios, textos, obras y análisis de obras. De esta investigación surge una topografía, un atlas de revelaciones de manifestaciones arquitectónicas: constataciones explícitas, testimonios implícitos o intuiciones. A través de este periplo entre el concepto de manifestación que la razón poética ofrece y la experiencia de muchos arquitectos se intenta responder, aunque sea parcialmente, a las preguntas que surgen al llevar a las últimas consecuencias la arquifanía: ¿En qué momento existe una voluntad de forma? ¿De qué manera encuentra el arquitecto la forma? ¿Cómo se le presenta? ¿Es el arquitecto el verdadero artífice de la obra? ¿O es en cambio un ser a la espera de la aparición? ABSTRACT Archiphany: architecture and epiphany. The revelation taking place in designing, building and living. The objective of the present dissertation is to unravel the protagonists and the scenario of this encounter. It stems from a double interest: the relationship between literature and architecture and the discovery of something incommensurable in architecture. Over the centuries, architectural theory has made a great effort in order to rationalise all aspects of this discipline. Thus, the systematization of the order and hierarchy of space, the use of more rigorous parameters on the structural analysis, the development of technical capacities and the study of functional schemes have been an inexhaustible source of architectural manifestations. Even scientific paradigms have been essential in the creation of new languages. However, aspects of difficult quantification have been relegated in this path of rationalisation. Whereas the presence of immeasurable parameters are encountered in the daily experience of the architect, architectural theory has failed to systematically integrate this knowledge. This is the driving force of this thesis. It explores, by analogy with the other arts, the concept of manifestation. It discusses how the architectural work manifests itself, making use of its autonomy, becoming the one leading the architect during the whole existence of the work: from its genesis in the designing time until the experience of the completed work in the historical time. In the present dissertation, it is assumed that reflecting on the concept of manifestation might shed light on two different moments on the way to project architecture. The architect approach to the project genesis is studied on the one hand, while in the other hand it is considered his positioning in front of the existing work, as well as his analysis (for a following synthesis) that generates an ever-open and ever-enriching spiral of knowledge. In the search for a definition of the concept of manifestation, the work of the philosopher María Zambrano and the poet José Ángel Valente are analysed. The creative moment, the nature of the poetic word, the attitude of the poet in front of his work, the knowledge and the revelation of beauty are persistent issues in their works. They create a theoretical corpus allowing to develop a sound and open poetical theory full of suggestions, accurately directed to the time of the form generation: its epiphany. The concept of manifestation is then reviewed in the activity of some modern artists that talked about the concept of epiphany –either implicitly or explicitly. Often in an intuitive way, artists have come to realize in their activity to be the depositories of a gift that is renewed in each work. Intertwined with their work and with their daily discipline, artists experience a dialogue with the work, which proves to be free and willing to manifest itself. Having stated the problem and having reviewed the world of artistic creation, we are confronted with the core of the thesis: Up to which extent and in which way is the concept of manifestation valid for architecture? Validity and evidence of this concept is sought in the activity of multiple architects. Texts, works, analysis, reviews and testimonies are investigated. From this research, a topography, an atlas of revelations of architectural manifestations arises: explicit findings, implicit witnesses or intuitions. By means of this journey going from the concept of manifestation hinted by the poetic reason to the experience of many architects, the ultimate questions risen by archiphany are meant to be answered (though partially): When does a will of form emerge? How does the architect find the form? How does it appear? Is the architect the true creator of the work? Or is he instead a being waiting for the vision?