Análisis de sistemas de máquinas de estados finitos en comunicación

An´alisis de sistemas de M´aquinas de Estados Finitos en comunicaci´on Analysis of Communicating Finite State Machines Pablo Hidalgo Palencia DOBLE GRADO EN INGENIER´ IA INFORM´ ATICA Y MATEM´ ATICAS FACULTAD DE INFORM´ ATICA UNIVERSIDAD COMPLUTENSE DE MADRID Trabajo de Fin de Grado de Ingenier´ıa Inform´atica Curso 2019/2020 Directores: Ismael Rodr´ıguez Laguna Fernando Rosa Velardo i Resumen En este trabajo presentamos un modelo de c´omputo formado por varias m´aquinas de estados finitos que se pueden comunicar entre s´ı a trav´es de canales FIFO. Estudiamos cu´al es su expresividad y la complejidad de resolver algunos problemas en este modelo, que yace entre lo decidible y lo indecidible por aunar la simplicidad de las m´aquinas de estados finitos con la complejidad que aportan comunicaciones no deterministas. Estudiamos adem´as diversas variaciones en la definici´on y las implicaciones que tienen estas modificaciones sobre la expresividad y complejidad del modelo. Palabras clave M´aquinas de estados finitos, m´aquinas de estados finitos en comunicaci´on, sistemas de mensajes perdidos, redes de Petri, aut´omata 110. ii Abstract In this work we present a computation model in which several Finite State Machines communicate via FIFO channels. We study its expressivity and the complexity of solving some decision problems regarding this model, lying on the edge between decidability and undecidability because of bringing together the simplicity of Finite State Machines and the complexity of non-deterministic communications. We also study some variations of the main model and the changes they generate in terms of expressivity and complexity. Keywords Finite State Machines, Communicating Finite State Machines, Lossy Channel Systems, Petri nets, rule 110. ´ Indice general 1. Introducci´on 1 2. Estado del arte 5 3. Definici´on de los sistemas con 2 m´aquinas 7 3.1. Sistemas donde los outputs no proliferan ................ 10 4. Expresividad de los sistemas 12 5. Definici´on general de los sistemas 15 5.1. Sistemas con buffers acotados ...................... 17 6. Sistemas donde los outputs no proliferan 19 6.1. Ejemplo de funcionamiento ....................... 19 6.2. Expresividad de los sistemas donde los outputs no proliferan . . . . 21 7. Sistemas con buffers acotados 32 8. Sistemas con buffers sin orden 35 8.1. Expresividad de los sistemas con buffers sin orden .......... 36 8.2. Comparativa con otros tipos de redes de Petri ............. 39 9. Sistemas de Mensajes Perdidos 43 9.1. Introduciendo justicia en las ejecuciones ................ 44 10.Complejidad de algunas propiedades 47 10.1. El problema de la alcanzabilidad finita ................. 47 10.1.1. En sistemas con buffers acotados ................ 51 10.2. El problema de regreso al estado inicial ................ 52 10.3. Otros problemas de complejidad mayor ................. 58 iii ´ INDICE GENERAL iv 11.Un sistema Turing universal 61 12.Conclusiones 67 Cap´ıtulo 1 Introducci´on En la literatura cient´ıfica, en particular en la de la Inform´atica, es frecuente encontrarse situaciones en las cuales los investigadores tienen un problema que resolver que no se ajusta perfectamente a ning´un modelo preestablecido conocido, si bien puede ser solventado de forma sencilla creando un modelo ad hoc para la situaci´on a partir de otros ya estudiados en profundidad. Por ejemplo, en numerosas ocasiones, al enfrentarse a ciertos problemas, los autores deciden dividir el problema en varias secciones sencillas e interconectarlas entre s´ı. Notemos que esto tambi´en se hace en la vida real: la mayor´ıa de los trabajos complejos se suelen realizar dividi´endolos en partes m´as peque˜nas y sencillas (que podr´an ser´an realizadas por diferentes personas) y despu´es junt´andolas. Este es el caso de nuestro estudio: es frecuente que al tener que modelizar protocolos concurrentes en la Inform´atica, por ejemplo, se utilice la misma t´actica que coment´abamos. En concreto, el protocolo se realiza por medio de instancias peque˜nas m´as sencillas, como pueden ser las que realizan las m´aquinas de estados finitos, elementos bastante sencillos y estudiados; estableciendo una comunicaci´on entre las distintas m´aquinas para que puedan simular el protocolo completo. No obstante, estas construcciones complejas hechas a partir de m´aquinas de estados sencillas se suelen hacer ad hoc para la situaci´on en la que se est´e interesado, y esto hace que en general no se puedan reutilizar ciertos resultados ya existentes en ejemplos similares en la literatura. En este trabajo pretendemos hacer un estudio m´as general sobre estos sistemas formados por m´aquinas de estados en comunicaci´on, de forma que pueda establecer unas bases para saber qu´e propiedades podr´ıa tener un sistema concreto que utilicemos en otros trabajos con un fin m´as determinado. Por ejemplo, si para una investigaci´on posterior usamos un modelo similar a los que vamos a explicar en este estudio, ¿resultar´an propiedades de decisi´on b´asicas como terminaci´on o alcanzabilidad decidibles o tratables? Los resultados que veremos en los siguientes cap´ıtulos ayudar´an a responder este tipo de preguntas. Adem´as, dada la variabilidad y versatilidad de este tipo de sistemas, resultar´a interesante investigar sus propiedades en funci´on de los diferentes tipos de definici´on que podamos hacer de ellos, por lo cual trataremos varios tipos de sistemas para poder establecer comparativas entre sus propiedades, lo que creemos que podr´ıa ser de utilidad a la hora de vernos en la necesidad de usar alguno de estos sistemas. El texto ir´a organizado por cap´ıtulos. En el cap´ıtulo 2daremos una visi´on amplia sobre literatura relacionada con nuestro trabajo. En el cap´ıtulo 3veremos una 1 Cap´ıtulo 1 - Introducci´on 2 definici´on de un modelo simplificado de los sistemas de m´aquinas de estados en comunicaci´on, que nos ayudar´a a comprender mejor los conceptos antes de entrar en el caso general. En el cap´ıtulo 4veremos que esta simplificaci´on de los sistemas es un modelo Turing completo. Con esto, en el cap´ıtulo 5llegamos ya a la definici´on de los sistemas generales que trataremos a partir de ah´ı. En el cap´ıtulo 6estudiaremos m´as a fondo el caso de los sistemas donde los outputs no proliferan, que resultan ser, como reconocedores de lenguajes, un modelo completo dentro del de los dependientes del contexto. En el siguiente cap´ıtulo, el 7, explicamos que los sistemas donde los buffers est´an acotados no pueden reconocer m´as all´a de los lenguajes regulares. En el cap´ıtulo 8estudiamos qu´e ocurre en el caso de que se pierda el orden de los mensajes intercambiados en nuestros sistemas, ya que obtenemos modelos comparables a diferentes tipos de redes de Petri, los modelos m´as representativos cuando no hay orden en los sistemas. M´as tarde, en el cap´ıtulo 9, estudiamos qu´e ocurre cuando otra propiedad b´asica de los sistemas cambia, concretamente qu´e ocurre cuando los canales de comunicaci´on pueden fallar, y su relaci´on con los conocidos Sistemas de Mensajes Perdidos. Tras todo esto, llegamos al cap´ıtulo 10, donde estudiamos la complejidad de resolver diferentes problemas de decisi´on sobre las cualidades de nuestros sistemas, centr´andonos en el problema de la alcanzabilidad finita y de regreso al estado inicial. Por ´ultimo, presentamos en el cap´ıtulo 11 un sistema bastante sencillo que es Turing universal, por medio de una simulaci´on del aut´omata 110. Introduction As we can see in the existing scientific literature, it is quite usual that a researcher faces a problem which does not fit exactly in an existing model, but can be easily solved creating an ad hoc model for this situation based on others which have been studied in depth. For instance we can find the situation where a researcher splits a problem into smaller and simpler sections and then connects all them properly. Notice that this is not a unique feature from research, we do this in our daily life: we carry out the vast majority of the difficult works using a strategy that first divides the whole task into smaller subtasks (which are commonly done by different people) and then join everything. This will be our case: for instance it is common that the strategy explained above is used when modelling concurrent protocols in Computer Science. More concretely, the protocol is carried out by means of smaller systems, such as Finite State Machines -which are really simple and have been studied broadlywhich can join their efforts if we establish some kind of communication among them. Although this is a common situation, these complex constructions are often in practice really ad hoc, in the sense that they are not directly reusable in other situations than the one they were thought for. This makes it more difficult to reuse not only the definitions, but also the results and properties that were proved for those models. In this work we aim to study in a broad generality this kind of systems where some Finite State Machines can communicate among them, with the purpose of establishing some foundation in the topic which can be later used to know which kind of properties are to expect from a concrete similar model that anyone could need in a research. If it were the case that we used a similar model in another work, would some basic properties of that model such as termination or reachability be decidable or tractable? The results we are about to develop in the next chapters will help to answer this sort of questions. Furthermore, given the variability and flexibility of this kind of systems, it will be of great interest to investigate their properties in terms of the different definitions we can use, in order to state a comparative among some of the possible models that can be created from the same abstraction. This can turn out to be really useful when deciding which model best fits a concrete situation we are interested in. The text will be divided into chapters. In Chapter 2we will take a look at the existing literature related to our work. In Chapter 3we will introduce the topic by studying a simplified version of our final model, which only comprises a maximum of two Finite State Machines, and will help us understand better the key concepts. In Chapter 4we prove that this simplified model is Turing complete. In Chapter 5 we arrive to the definition of the main model we are interested in. In Chapter 6we 3 Cap´ıtulo 1 - Introducci´on 4 study a submodel where the amount of information used to communicate is limited (the Finite State Machines can communicate with only one machine at a time), which results to be complete among the context-sensitive language recognizers. We study next, in Chapter 7, the case where the size of the buffers used to communicate is bounded, which results in a model that can only recognize regular languages. In our path studying variations of the main model we get to the Chapter 8, where the order of the messages exchanged between machines is in some sense lost, and the resulting model is comparable to different kinds of Petri nets. In Chapter 9we study the case where another crucial property of the communications is changed: if the channels used for communications are faulty, the formalism becomes really similar to Lossy Channel Systems, and we will study the connections more in detail. All this been studied we arrive to Chapter 10, where we look into some decision problems on our models and their complexity, focusing on some finitary versions of reachability and home-state problems. Finally in Chapter 11 we present a really simple system which is (Turing-)universal, based on Rule 110. Cap´ıtulo 3 - Definici´on de los sistemas con 2 m´aquinas 11 como mucho tantos outputs como inputs consumen, deducimos que la cantidad de literales en S, es decir, |B1|+|B2|nunca puede crecer a lo largo de cualquier ejecuci´on. Cap´ıtulo 4 Expresividad de los sistemas Una vez claras las definiciones, vamos a estudiar primeramente cu´al es la expresividad de los sistemas que acabamos de definir. Va a resultar interesante comprobar que, a pesar de la simplicidad de las definiciones, los sistemas de FSMs en comunicaci´on son Turing completos. Para la demostraci´on de este hecho nos basaremos en una comparativa con los aut´omatas con cola, que presentamos aqu´ı brevemente. Definici´on 4.1. Un aut´omata con cola Mes una tupla M= (Q, Σ,Γ,$, q0, δ), donde Qes un conjunto (finito) de estados, Σ⊂Γes el alfabeto usado por los inputs, Γes el alfabeto que usa la cola, $∈Γ\Σes el s´ımbolo inicial de la cola, q0∈Qes el estado inicial de Myδ:Q×Γ→Q×Γ∗es la funci´on de transici´on. La funci´on de transici´on act´ua de forma similar al caso de los aut´omatas con pila, que tambi´en utilizan cierta memoria adicional, pero en esta ocasi´on utilizando una estrategia LIFO: las transiciones toman un literal del principio de la cola y devuelven varios literales que se meten por el final de la cola. Cabe mencionar tambi´en que los aut´omatas con cola aceptan por cola vac´ıa. Lo m´as interesante para nosotros en este momento es que los aut´omatas con cola forman un sistema Turing completo, pues pueden simular cualquier m´aquina de Turing, y de hecho en tiempo polin´omico (como se puede consultar en [19], ejercicio 99, por ejemplo). De esto resulta que una demostraci´on sencilla de la Turing completitud de los sistemas de FSMs en comunicaci´on se base en reducir un aut´omata con cola a uno de estos sistemas. Adem´as, aunque no hace falta para probar la Turing completitud, esta reducci´on se puede hacer polin´omica, lo cual ser´a de utilidad posterior para demostrar otras propiedades. En el siguiente resultado vamos a desarrollar esta idea en profundidad. Teorema 4.2. El conjunto de sistemas de FSMs en comunicaci´on en los cuales los outputs proliferan (seg´un la definici´on 3.1) es Turing completo. Demostraci´on. Sea M= (Q, Σ,Γ,$, q0, δ) un aut´omata con cola, seg´un la definici´on anterior 4.1. Entonces podemos crear un sistema S= (F1, F2), con buffers B1, B2, de dos m´aquinas en comunicaci´on que simulen el comportamiento de Mde forma que F1simule las transiciones de M(a trav´es de la funci´on de transici´on δ1), mientras que F2simplemente haga que todos los inputs que le llegan desde B2 acaben en B1(a trav´es de δ2). De esta forma, al ser los buffers colas, se comportar´an como la cola de nuestro aut´omata M. No obstante, hemos de poner atenci´on a la hora de definir F1, pues la forma que tiene Mde hacer que los outputs proliferen es generando varios literales con una 12 Cap´ıtulo 4 - Expresividad de los sistemas 13 misma transici´on (recordemos δ:Q×Γ→Q×Γ∗), mientras que F1lo hace un tanto diferente, a trav´es de su funci´on de transici´on δ1:Qi×Σ?−→ Q1×Σ?. En el primer cap´ıtulo ya vimos la intuici´on de que realmente estas dos formas de hacer proliferar los outputs eran equivalentes, y aqu´ı vamos a ver la construcci´on que necesitamos m´as en detalle. Para cada estado qi∈Q,F1tendr´a asimismo un estado q1 i∈Q1. Veamos ahora qu´e construcci´on hacemos para simular una transici´on arbitraria δ(qi, X) = (qj, α) de M. Si el tama˜no de αes n∈N, podemos decir que α=Y1+Y2+. . .+Yn, donde Yk∈Σ son literales de nuestro alfabeto. En el caso de que n < 2 podemos simular f´acilmente la transici´on de δincluyendo δ1(q1 i, X)=(q1 j, α). Y en el caso de que n≥ 2, simplemente tenemos que a˜nadir n−1 estados auxiliares q1 i,X,1, q1 i,X,2,··· , q1 i,X,n−1, junto con las transiciones δ1q1 i, X=q1 i,X,1, Y1,δ1q1 i,X,1, =q1 i,X,2, Y2,. . ., δ1q1 i,X,n−2, =q1 i,X,n−1, Yn−1. La construcci´on la podemos ver gr´aficamente como en la siguiente figura: qiqj X/α se convierte en: q1 iq1 i,X,1q1 i,X,2q1 i,X,n−1q1 j X/Y1/Y2··· /Yn Figura 4.1: Visualizaci´on de la transformaci´on para que las FSMs solo produzcan un output con cada transici´on. Tenemos que tener en cuenta ahora que hay que simular la aceptaci´on de M, que como dijimos es por cola vac´ıa. Al igual que se hace usualmente con los aut´omatas con pila, en los cuales se introduce un s´ımbolo especial que denota el fin de la pila, aqu´ı introduciremos el s´ımbolo # con el mismo fin. Lo primero que har´a F1 ser´a generar dicho literal desde su estado inicial q1 #, que tendr´a una ´unica transici´on: δ1(q1 #, ) = (q1 0,#), donde q1 0es el estado asociado al estado inicial q0de M. A partir de ah´ı, F1no tendr´a en cuenta el literal #, pues no influye en la simulaci´on de M. Por ello, cada estado q∈Q1obviar´a las # mediante la transici´on δ1(q, #) = (q, #). Visto esto, la m´aquina F2ser´ıa realmente simple, como explic´abamos en la discusi´on anterior: podr´ıa simplemente contar con un estado q2 0(que ser´ıa el estado inicial de F2), y con las transiciones δ2(q2 0, A)=(q2 0, A) para todos los A∈Γ, de forma que lo ´unico que hace es devolver lo que lee. Y tiene que tener tambi´en un mecanismo de detectar la aceptaci´on. Como tenemos que simular la aceptaci´on de M, que es por cola vac´ıa, Sdeber´ıa aceptar cuando sus buffers est´an vac´ıos. Pero para ello hemos introducido el s´ımbolo #: cuando Sllegue a simular a Mcon la cola vac´ıa, el ´unico s´ımbolo que habr´a en los buffers B1, B2ser´ıa #. Por tanto, F2 Cap´ıtulo 4 - Expresividad de los sistemas 14 puede aceptar en cuanto vea # dos veces seguidas. Una representaci´on gr´afica se puede ver en la figura 4.2. q2 0q2 #q2 f #/# A/A (A6= #) #/ A/A (A6= #) Figura 4.2: La FSM F2de nuestro sistema. De esta forma, el sistema que conforman F1,F2simula el aut´omata M, usando el alfabeto Γ∪{#}, con estados iniciales (q1 #, q2 0)∈Q1×Q2y estado final q2 f∈Q2. Notemos adem´as que por cada output que genera M, para simular dicha producci´on de un output nuestro sistema Sproduce ´unicamente 2 outputs (uno F1y otro F2) Esto quiere decir que los tiempos de ejecuci´on de MySse relacionan tambi´en con ´unicamente ese factor constante 2. Por tanto, la simulaci´on se hace en tiempo polin´omico respecto a lo que tarda M(por cada paso de M,Sda una cantidad O(1) de pasos). En cuanto a espacio tambi´en tenemos una transformaci´on polin´omica, lo cual podemos ver en la cantidad de estados de F1yF2. Y como la reducci´on de m´aquinas de Turing a aut´omatas con cola se puede hacer tambi´en con ´unicamente un aumento polin´omico de tiempo y espacio, concluimos que la reducci´on de m´aquinas de Turing a sistemas de FSMs en comunicaci´on es polin´omica. Cap´ıtulo 5 Definici´on general de los sistemas Visto ya el inter´es que tienen los sistemas de FSMs en comunicaci´on a trav´es de su gran expresividad a pesar de su aparente sencillez, como acabamos de comprobar al ver que conforman un sistema Turing completo, pasamos a estudiar una generalizaci´on natural de los sistemas que hab´ıamos considerado hasta ahora, introduciendo un mayor n´umero de FSMs. Sean Fi= (Qi, Ii, Oi, q0 i, δi), con 1 ≤i≤n, un conjunto de nFSMs. Definimos S= (F1, F2, . . . , Fn) como el sistema de FSMs en comunicaci´on asociado a F1, . . . , Fn. Estas m´aquinas se comunican entre s´ı a trav´es de ciertos buffers B1, B2, . . . , Bn, de forma que Ficonsume literales de Bi(desde uno de los extremos del buffer), mientras que cualquier m´aquina puede escribir literales en Bi(por el extremo contrario al que Filee). La configuraci´on de Sdepender´a en cada instante del estado en que est´a cada m´aquina Fiy del contenido de cada buffer Bi. Cabe destacar que en este caso vamos a interpretar los outputs de cada m´aquina Fide una manera que nos va a resultar m´as c´omoda. Podemos suponer que cada funci´on de transici´on ha cambiado su rango: δi:Qi×I? i−→ Qi×O? in(donde Qi×O? in⊆Qi×I? 1×I? 2×···×I? npara que la comunicaci´on tenga sentido), ya que ahora cada transici´on de Fiva a generar (potencialmente) un output para cada una de las m´aquinas de S. Notamos adem´as que, al igual que en el caso m´as sencillo en el cual solo ten´ıamos 2 m´aquinas, los correspondientes alfabetos de las m´aquinas tienen que ser coherentes entre s´ı para que se pueda establecer una comunicaci´on entre ellas. En una situaci´on general, deber´ıamos tener Oi⊆Ijpara cada par 1≤i, j ≤n, de forma que Fjentiende los literales que le manda Fi. En los casos donde no sea necesario (y de hecho, resulte engorroso) lidiar con esta suerte de detalles, denotaremos Σ := I1∪I2∪···∪In∪O1∪O2∪···∪Oncomo el alfabeto de todas las m´aquinas de Spor simplicidad, ya que generaliza al resto de alfabetos. La funci´on de transici´on global entre las distintas transiciones de Stoma ahora la forma δ:Q1×Σ∗×Q2×Σ∗×···×Qn×Σ∗−→ Q1×Σ∗×Q2×Σ∗×···×Qn×Σ∗ entre las diferentes configuraciones de Sque nos ayuda a saber c´omo evoluciona este sistema. Esencialmente, simula ejecuciones de cada m´aquina por separado, igual que en el caso de ´unicamente dos m´aquinas, de forma que en cada transici´on de Shay una m´aquina Fique da un paso en su ejecuci´on: lee de su buffer Bi, avanza en la direcci´on que le indique ese literal le´ıdo y env´ıa al resto de m´aquinas los literales que la transici´on le indique, dej´andolos en sus respectivos buffers. Vista la intuici´on, escrib´amoslo de manera m´as precisa. 15 Cap´ıtulo 5 - Definici´on general de los sistemas 16 Definici´on 5.1. Sea un conjunto de nFSMs, F1, F2, . . . , Fn, donde cada m´aquina es Fi= (Qi, Ii, Oi, q0 i, δi), con funci´on de transici´on δi:Qi×Σ?−→ Qi×Σ?n, como antes hemos descrito. Definimos entonces el sistema de FSMs en comunicaci´on asociado a estas m´aquinas como S= (F1, F2, . . . , Fn). Una configuraci´on de Ses una tupla de Q1×Σ∗×Q2×Σ∗×···×Qn×Σ∗. Adem´as, la funci´on de transici´on de S,δ, tiene transiciones que simulan pasos de las distintas FSMs Fi, con 1≤i≤n, pues est´a definida de la siguiente forma: Bi=X+B0 i∧δi(qi, X)=(q0 i, α1, α2, . . . , αn) =⇒ (q1, B1+α1, . . . , qi−1, Bi−1+αi−1, q0 i, B0 i+αi, qi+1, Bi+1 +αi+1, . . . , qn, Bn+αn) ∈δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn) De nuevo, una configuraci´on (q1, B1, . . . , qn, Bn) de Sse puede entender como el conjunto de estados q1, . . . , qnen que est´an las distintas FSMs y el contenido de los buffers B1, . . . , Bnen ese determinado instante. Desde una de sus configuraciones, el sistema puede transitar a otras configuraciones con literales distintos de (como mucho habr´a nde este tipo), aquellas que resultan de avanzar un paso en la ejecuci´on de cada una de las m´aquinas que no tengan su buffer de lectura vac´ıo (y que su funci´on de transici´on les permita avanzar), y de modificar los buffers adecuadamente con respecto a lo que dicta esta transici´on. Pero tambi´en hay otro tipo de transiciones: las asociadas a pasos en los cuales cada FSM consume de su buffer correspondiente, es decir, avanza sin consumir ning´un literal. Adem´as, recuperamos el concepto de configuraci´on de aceptaci´on que ya ten´ıamos en el caso de sistemas con ´unicamente 2 m´aquinas: nuestro sistema Stiene un conjunto de estados finales QF⊆Q1∪Q2∪. . . ∪Qnde forma que una configuraci´on (q1, B1, q2, B2, . . . , qn, Bn) es de aceptaci´on qi∈QFpara alg´un ´ındice i∈ {1, . . . , n}. De igual manera, la forma en que estos sistemas reconocen palabras es la misma que la que usaban sus an´alogos con ´unicamente dos m´aquinas y que explicamos en 3: consideraremos que un sistema acepta una palabra si una configuraci´on de aceptaci´on es alcanzable tras comenzar en la configuraci´on inicial que surge de tener a cada FSM en su estado inicial y todos los buffers vac´ıos, excepto el de la (sin p´erdida de generalidad) primera m´aquina, que contiene dicha palabra. En estos sistemas el fen´omeno de proliferaci´on de los outputs es todav´ıa m´as claro: adem´as de lo que ocurr´ıa en el caso con ´unicamente dos m´aquinas, que aqu´ı tambi´en se da (pues seguimos pudiendo generar outputs sin consumir inputs), por cada transici´on de una m´aquina se est´a consumiendo un literal (a lo sumo), mientras que potencialmente se podr´ıan generar nliterales como output, lo cual hace que se puedan generar muchos m´as outputs que los inputs que se consumen. De hecho, podemos tener una situaci´on en la cual haya m´aquinas que solo retransmiten lo que les llega a otra m´aquina. Por ejemplo, si F1quisiera mandarle dos literales, AB, a F2, podr´ıa utilizar una m´aquina intermediaria F3:F1mandar´ıa AaF2yBaF3, y despu´es F3retransmitir´ıa esa Bpara que le llegara a F2. De esta forma, estar´ıamos consiguiendo mandar mensajes con m´as de un literal de F1 aF2sin que nunca a˜nadamos m´as de un literal a cada buffer en cada transici´on, lo cual nos indica que el fen´omeno de proliferaci´on de los outputs es completamente Cap´ıtulo 5 - Definici´on general de los sistemas 17 inherente a la definici´on de estos sistemas, pues se puede conseguir incluso con la limitaci´on de que no se pueden generar outputs sin consumir inputs. De esta forma, al ser la proliferaci´on de los outputs un fen´omeno tan inherente a este tipo de sistemas, no nos deber´ıa molestar el hecho de que una FSM se pueda mandar mensajes tambi´en a s´ı misma (que en principio podr´ıa no parecer la mejor opci´on), pues siempre podr´ıamos introducir una m´aquina intermediaria con el mismo prop´osito (como comentamos en el p´arrafo anterior). Por tanto, no tendr´ıa sentido limitar que una m´aquina no se pueda enviar mensajes a s´ı misma. A la vista de lo anterior, queda claro que la ´unica forma de evitar la proliferaci´on de los outputs en este tipo de sistemas es que cada transici´on genere a lo sumo un output cada vez que consigue un input. Esto se dar´ıa si δi:Qi×Ii−→ Qi× O? infunciona de forma que para cada transici´on δi(qi, α)=(q0 i, α1, α2, . . . , αn) a lo sumo una de las producciones α1, . . . , αnes distinto de . La ´unica manera de conseguir evitar el fen´omeno de proliferaci´on de los outputs ser´ıa por tanto hacer esta modificaci´on de nuestra definici´on. Por ello, al ser inherente a estos sistemas el fen´omeno de proliferaci´on de los outputs, podemos modificar ligeramente la definici´on de las FSMs que usamos, de forma que sean m´as c´omodas de utilizar. En vez de considerar que la funci´on de transici´on de la m´aquina Fies δi:Qi×Σ?−→ Qi×Σ?n, podemos considerar equivalentemente δi:Qi×Σ?−→ Qi×(Σ∗)n, lo cual nos simplificar´a algunos razonamientos en cap´ıtulos venideros. En realidad esto es simplemente una extensi´on de los argumentos que coment´abamos a la hora de definir sistemas con solo dos FSMs, y que demostramos con mayor formalidad en el teorema 4.2, y por tanto no creemos que sea necesario incidir m´as en ello. Notemos asimismo que este tipo de sistemas son Turing completos, pues ya hemos probado en el cap´ıtulo anterior que una subclase suya, en la que restringimos el n´umero de m´aquinas a ´unicamente 2, ya es Turing completa (como vimos en el teorema 4.2). 5.1. Sistemas con buffers acotados Para poder seguir estableciendo comparativas que nos ayuden a comprender qu´e caracter´ısticas de los sistemas de FSMs en comunicaci´on son los que realmente le dan su gran expresividad, vamos a estudiar otra modificaci´on, en la que esta vez hay una limitaci´on en cuanto a la memoria que el sistema puede usar. Definici´on 5.2. Decimos que un sistema de FSMs en comunicaci´on S= (F1, F2, . . . , Fn) es un sistema con buffers acotados si existe una constante Mde manera que en cada una de las configuraciones (q1, B1, q2, B2, . . . , qn, Bn)alcanzables de S, el tama˜no de cada buffer es a lo sumo M, es decir, |Bi| ≤ M∀1≤i≤n. Esta limitaci´on podr´ıa parecer excesiva una vez que nos damos cuenta de que en realidad, dada la capacidad finita de los buffers, en realidad este tipo de sistemas solo pueden recibir inputs de una longitud acotada por M(o Mn en caso de que Cap´ıtulo 5 - Definici´on general de los sistemas 18 distribuy´eramos de alguna forma dichas instancias sobre los cuales el sistema se ejecuta en los diferentes buffers). Esto har´ıa que los ´unicos lenguajes que se pudieran reconocer con este tipo de sistemas fueran una subclase de los lenguajes finitos, un estadio muy pobre en la jerarqu´ıa de Chomsky. Para evitar esta situaci´on un tanto indeseable, pues el hecho de que las m´aquinas est´en en comunicaci´on no a˜nadir´ıa nada a su capacidad expresiva, vamos a hacer una peque˜na modificaci´on. Podemos considerar que hay una m´aquina F0que es la que recibe los inputs del sistema, y por tanto su buffer no est´a acotado, es una FSM normal. Pero si dejamos que esta m´aquina participe en la comunicaci´on con el resto de m´aquinas, realmente la hip´otesis de que los buffers est´an acotados no tendr´ıa ya mucho sentido, pues se podr´ıa usar el de F0, que no lo es. Por tanto, debemos mantener a F0al margen de estas comunicaciones. Podemos imponer que lo ´unico que haga F0sea enviar inputs poco a poco a (sin p´erdida de generalidad) F1, siempre que B1no est´e lleno, y que F0no interact´ue de ninguna otra manera dentro del sistema. En concreto, no puede recibir mensajes de ninguna m´aquina. De esta forma, queda claro que estamos respetando la restricci´on de los buffers acotados: todos los c´omputos que hace Sutilizan solo los buffers acotados; mientras que el truco de a˜nadir F0no mejora las caracter´ısticas de S, sino que solo permite que adem´as se procesen palabras de longitud arbitraria como input, lo cual es bastante m´as razonable para un modelo de c´omputo. Cap´ıtulo 6 Sistemas donde los outputs no proliferan Si reducimos la capacidad de comunicaci´on de nuestros sistemas de FSMs no permitiendo que proliferen los outputs como en las situaciones anteriores, tiene sentido pensar que la expresividad de estos sistemas caer´a, y puede que no est´en como en el caso anterior a la misma altura que las m´aquinas de Turing en la jerarqu´ıa de Chomsky. Pero tampoco pierden demasiada expresividad, pues pueden reconocer lenguajes que no son incontextuales, como el de las palabras del tipo w#w, con w∈Σ∗para alg´un alfabeto no trivial, como por ejemplo Σ = {0,1}(lo cual veremos en m´as detalle a continuaci´on). Esto nos sugiere buscar un estadio intermedio entre los aut´omatas con pila y las m´aquinas de Turing, como los aut´omatas linealmente acotados (LBA por sus siglas en ingl´es). En este caso, esta intuici´on va a ser correcta, pues va a existir una equivalencia de expresividad entre los LBA y nuestros sistemas de FSMs donde los outputs no proliferan. Recordamos brevemente la definici´on de un LBA: Definici´on 6.1. Se dice que F= (Q, Γ, [, q0, QF, δ)es un LBA si es una m´aquina de Turing (con estados Q, alfabeto Γ, s´ımbolo de blanco [, estado inicial q0, estados de aceptaci´on QFy funci´on de transici´on δ:Q×Γ−→ Q×Γ×{←,→}) de forma que a lo largo de toda la ejecuci´on procesar un input solo utiliza una cantidad de posiciones de su cinta que es lineal en el tama˜no de dicho input. Es decir, ante un input de tama˜no n, un LBA solo puede utilizar una cantidad O(n) de posiciones de su cinta; y por lo dem´as se comporta como una m´aquina de Turing usual. En concreto, se suelen usar s´ımbolos delimitadores como `,aen ambos extremos de la cinta para que quede claro que la cantidad de cinta que se puede usar est´a acotada desde el principio. Se puede consultar m´as sobre ellos en, por ejemplo, el cap´ıtulo 9.3 de [17]. 6.1. Ejemplo de funcionamiento Vista la anterior intuici´on sobre en qu´e nivel de la jerarqu´ıa de Chomsky podr´ıan situarse los sistemas de FSMs en los cuales los outputs no proliferan, consideramos ´util desarrollar m´as el ejemplo anterior para ver m´as en detalle un ejemplo en el cual la comunicaci´on que se establece entre dos FSMs sencillas es suficiente para reconocer un lenguaje un tanto complejo, que no es incontextual. 19 Cap´ıtulo 6 - Sistemas donde los outputs no proliferan 20 Proposici´on 6.2. El lenguaje L=w#w:w∈ {0,1}∗no es incontextual, pero puede ser reconocido por un sistema de FSMs en comunicaci´on donde los outputs no proliferan. Demostraci´on. Demostramos los dos asertos por separado: Lno es incontextual. Lo demostramos con una aplicaci´on del lema del bombeo. Suponiendo que Lfuera incontextual, sea nes la constante del lema del bombeo de L. Considerando la palabra 0n1n#0n1n∈L, tendr´ıa que admitir una descomposici´on 0n1n#0n1n=uvwxy, con |vwx| ≤ n,|vx| ≥ 1. Demostraremos que uv2wx2y /∈Lpara cualquiera de estas descomposiciones (llegando por tanto a una contradicci´on). Como # no se puede duplicar sin que la palabra salga de L, tenemos 3 opciones: 1. # ∈w. En ese caso, como |vwx| ≤ n, tenemos que v= 1a,x= 0b, donde al menos uno de entre aybes estrictamente positivo por ser |vx| ≥ 1. Si a > 0, en uv2wx2yse descompensar´an los unos en la palabra de la izquierda; y si b > 0, los ceros en la de la derecha. De ambos modos, uv2wx2y /∈L. 2. # est´a en uo m´as a su izquierda. Entonces en uv2wx2yser´a forzosamente m´as larga la palabra de la derecha, pues solo se bombea en ella. Y necesariamente uv2wx2y /∈L. 3. # est´a en yo m´as a su derecha. Es una situaci´on an´aloga al punto anterior. Pero, de hecho, podemos encontrar un sistema de FSMs en el cual los outputs no proliferan y que reconoce este lenguaje. Nuestro sistema ser´a S= (F1, F2). F1ir´a reconociendo las letras de la primera palabra, una a una, e ir´a confirmando que est´an en el mismo orden en la segunda palabra con la ayuda de F2, que ir´a resaltando las letras con las que deber´ıan coincidir. Un ejemplo de m´aquinas que podr´ıan hacer esta tarea ser´ıan las siguientes: 1. M´aquina F1: lo primero que hace es insertar [para simbolizar el fin de las palabras. Su funcionamiento es el siguiente: hace un barrido del buffer hasta que reconoce la primera letra (la de despu´es de [), y entra en un estado especial donde la recuerda, y la quita del buffer. Espera hasta que F2le manda una letra con barra arriba (que ser´an nuevos literales del alfabeto en los cuales nos apoyaremos en la construcci´on), que es la confirmaci´on de que despu´es de # ha venido esa letra. Si coincide con lo que recordaba, vuelve a empezar el ciclo, hasta que los buffers se vac´ıan, y en ese momento reconocer´ıa [#[y aceptar´ıa. Una versi´on gr´afica de la implementaci´on la podemos encontrar en 6.1. Cap´ıtulo 6 - Sistemas donde los outputs no proliferan 27 sistemas no pertenece a ning´un nivel inferior de la jerarqu´ıa de Chomsky pues, como vamos a demostrar, pueden simular cualquier LBA. Por tanto, son completos dentro de los aut´omatas dependientes del contexto. Veamos ahora esta demostraci´on. Cabe destacar que en este caso utilizaremos una definici´on un tanto distinta de los LBA, pues hay una definici´on equivalente que restringe la cantidad de cinta que puede usar un LBA a ´unicamente la que ocupa su input inicial. Esta versi´on, en la cual no permitimos una cantidad lineal de cinta extra, es equivalente, en t´erminos de capacidad de c´omputo, a la que propusimos anteriormente al definir los LBAs como consecuencia del Teorema del linear speedup en m´aquinas de Turing (se puede consultar en [17], cap´ıtulos 9.3, 12.2). Teorema 6.5. Cualquier LBA puede ser simulado por un sistema de FSMs en comunicaci´on donde los outputs no proliferan. Demostraci´on. Sea F= (Q, Σ, [, q0, QF, δF) un LBA. Vamos a definir un sistema S= (F1, F2) de FSMs donde los outputs no proliferan que simule F.F2ser´a una m´aquina muy sencilla, que simplemente devuelve todo literal que le llega. Podr´ıamos representarla del siguiente modo que nos muestra la siguiente figura: qx/x (∀x) Figura 6.7: Representaci´on gr´afica de F2. La m´aquina F1llevar´a toda la complejidad de simular F. Como Fes esencialmente una m´aquina de Turing usual, tiene una cinta, que intentaremos mantener en B1. Pero Ftiene adem´as un cabezal que puede modificar literales de cualquier posici´on de la cinta, mientras que F1solo puede tomar literales desde el principio de su buffer B1. Esto genera una dificultad, pero que se solventa de manera sencilla, como usualmente en estas situaciones: iterando sobre todo el buffer B1cada vez que Fd´e un paso. De esta manera, aunque de una forma un poco costosa, podemos simular cada movimiento de Fcon la generaci´on de un nuevo buffer B1, que ser´a la cinta de Fen el siguiente instante de tiempo. Adem´as, a la hora de simular esta cinta, aparecen ciertas dificultades. La primera es la de simular el cabezal de F. Lo solventaremos simplemente introduciendo m´as literales: por cada γ∈Σ, el nuevo literal ¯γ∈Γ del alfabeto de Ssignificar´a que en el buffer hay una γy adem´as en el cabezal est´a justo en esa posici´on. Se nos presenta tambi´en la dificultad de que el cabezal de Fpuede avanzar hacia la izquierda y a la derecha en la cinta, mientras que nuestra m´aquina F1solo puede leer su buffer en una direcci´on (digamos que de izquierda a derecha). La idea para solventar esto es simplemente retrasar un ciclo todas las decisiones de F1, pues as´ı nunca tomaremos decisiones incorrectas del siguiente tipo: si ten´ıamos α¯ β y tenemos que simular un movimiento a la izquierda del cabezal en una transici´on del tipo δ(q, β) = (q0, γ, ←), estos literales tendr´ıan que pasar a ser ¯αγ; pero solo nos damos cuenta de que αtendr´a el cabezal encima una vez que hemos visitado Cap´ıtulo 6 - Sistemas donde los outputs no proliferan 28 βy hemos visto que ella s´ı tiene el cabezal encima. Un esquema visual de estas producciones atrasadas ser´ıa el siguiente (at idenota el i-´esimo car´acter de la cinta en el instante t, y las flechas discontinuas denotan con la lectura de qu´e literal se generan otros literales): a0 0a0 1a0 2a0 3a0 4a0 5 a1 0a1 1a1 2a1 3a1 4a1 5 a2 0a2 1a2 2a2 3a2 4a2 5 Figura 6.8: Ejemplo explicativo de en qu´e momento se lleva a cabo cada producci´on. Adem´as tenemos que conseguir este retraso en la ejecuci´on sin que proliferen los outputs, lo cual no es inmediato de conseguir en una primera aproximaci´on al problema. Esto se puede solucionar introduciendo un car´acter # que indique el fin de la cinta de Fen nuestros buffers (es decir, que separe los buffers que se refieren a diferentes instantes de tiempo), lo cual sigue la idea de los LBA de delimitar la memoria que podemos utilizar. Con estas ideas en mente, pasemos a la implementaci´on de manera m´as concreta de la m´aquina F1. Lo primero es comentar que el alfabeto que usar´a el sistema S ser´a, como antes se indicaba: Γ := Σ ∪{¯γ:γ∈Σ}∪{#}. Para cada estado qi∈Qde Ftendremos un cluster de estados en F1que simular´an un barrido de la cinta de Fmientras est´a en el estado qi, cuyos estados denotaremos qi(adem´as de m´as sub´ındices para indicar la funci´on de esos estados dentro del cluster). En cada uno de estos clusters tenemos que implementar la idea anterior de retrasar la producci´on de outputs un ciclo, as´ı que tendremos que tener un estado diferente para cada literal de Γ para recordar cu´al es el literal que acabamos de ver. Adem´as, tenemos que conseguir simular las transiciones de F. Por ejemplo, si en Fhay una transici´on de qiaqjcuando el cabezal ve una A, nuestra m´aquina F1, en su cluster relativo a qi, tendr´a una transici´on diferente cuando vea ¯ A, pues transitar´a hacia una regi´on diferente del cluster en la cual recordaremos que el siguiente estado al que va a ir Fes qj. De esta forma, cuando le llegue la siguiente #, F1transitar´a hacia el cluster relativo a qj, y comenzar´a de nuevo a barrer la cinta de Fleyendo de su buffer. Para poder cumplir esto, cada cluster qitendr´a un conjunto de estados qγ i, con γ∈Σ∪ {#}, de forma que ejecutan la creaci´on del nuevo buffer antes de que se haya visitado la posici´on donde est´a el cabezal lector (es decir, van devolviendo exactamente lo que leen, pero un ciclo m´as tarde). Posteriormente, al ver el cabezal, hemos de distinguir si las diversas transiciones de Fen qimueven el cabezal a la Cap´ıtulo 6 - Sistemas donde los outputs no proliferan 29 izquierda o a la derecha, pues se nos generar´a una estructura diferente de estados en cada caso. Por ejemplo, si en Ftenemos una transici´on que mueve el cabezal lector hacia la izquierda, del tipo que nos muestra la siguiente figura: qiqj a/b, ← Figura 6.9: Representaci´on gr´afica de un ejemplo de transici´on que mueve el cabezal a la izquierda. Tenemos por tanto que tener una estructura de estados dentro del cluster asociado a qique pueda solventar esta situaci´on. Tendremos para ello un estado q0 i→jque visitaremos justo cuando hayamos visto el cabezal con una A, y que nos ayudar´a a transitar hacia una zona del cluster donde recordamos que el siguiente estado que visitar´a Fes qj. Una vez visitado q0 i→j, nos encontramos con otra regi´on del cluster donde lo ´unico que hacemos es copiar el buffer para la siguiente iteraci´on, al igual que hac´ıamos con los estados del tipo qγ i. Por eso llamamos a estos estados qγ i→j, pero esta vez ´unicamente con γ∈Σ, pues la llegada de una # nos har´a transitar hacia el cluster asociado a qj. Suponiendo, por simplicidad para la representaci´on gr´afica, que Σ = {a, b}(una vez visto el diagrama quedar´a claro que es sencillo generalizarlo a un alfabeto con m´as literales), podr´ıamos plasmar estas ideas sobre el cluster de qide la forma que nos indica la figura 6.10. q# i de otros clusters qa i qb i q0 i→j qa i→j qb i→j q# j cluster de qj. . . a/# b/# b/a a/b a/a b/b ¯a/¯a ¯a/¯ b a/b b/b b/a a/b a/a b/b #/a #/b Figura 6.10: Representaci´on gr´afica de la implementaci´on de un cluster simulando transiciones que mueven el cabezal hacia la izquierda. Cap´ıtulo 6 - Sistemas donde los outputs no proliferan 30 Y, en cambio, si la transici´on de Fmueve el cabezal a la derecha, tenemos que introducir algunos estados m´as para recordar los literales que vemos durante este movimiento. Supongamos entonces que tenemos en Ftenemos la transici´on entre qi, qj∈Q, del tipo de la figura siguiente: qiqj a/b, → Figura 6.11: Representaci´on gr´afica de un ejemplo de transici´on que mueve el cabezal a la derecha. Entonces en Ftendremos que tener una estructura del estilo de la mostrada en la figura 6.12 dentro del cluster relativo a q1, que es bastante similar a la anterior, pero donde introducimos algunos estados m´as q1,γ i→j, con γ∈Σ para recordar los literales que vemos justamente al llegar al cabezal (de nuevo supondremos Σ = {a, b}por simplicidad del diagrama): q# i de otros clusters qa i qb i q0 i→j q1,a i→j q1,b i→j qa i→j qb i→j q# j cluster de qj. . . a/# b/#a/a b/b b/a a/b ¯a/a ¯a/b a/b b/b a/¯a b/¯a a/¯ b a/¯ b b/a a/b a/a b/b #/a #/b Figura 6.12: Representaci´on gr´afica de la implementaci´on de un cluster simulando transiciones que mueven el cabezal hacia la derecha. Naturalmente, desde un estado qide Fpodr´ıa darse el caso de que hubiera transiciones a m´as de un estado del tipo qjen los ejemplos anteriores. Esto har´ıa Cap´ıtulo 6 - Sistemas donde los outputs no proliferan 31 que nuestro cluster asociado a qifuera m´as grande, ya que para cada transici´on de qiaqj, el cluster deber´ıa contener una estructura de estados qi→j. Es decir, dentro de un mismo cluster, tendremos que tener tantas estructuras del tipo qi→jcomo transiciones tenga Fen qi. De esta forma, en el cluster del estado qide Ftenemos una columna de estados en los cuales no hemos visto todav´ıa la posici´on del cabezal (los qγ i, despu´es una serie de estados (un conjunto de estados por cada transici´on saliente de qien F) que manejan el tratamiento del literal con el cabezal y la transici´on de F(los q0 i→j, q1,γ i→j), y una serie de columnas de estados (tambi´en una por cada transici´on de qi) que recuerdan a qu´e estado transita Fy, por tanto, cu´al es el siguiente cluster al que ir´a F1(los estados del tipo qγ i→j). As´ı podemos ir simulando transiciones de F, que modifican un par de posiciones de la cinta, con un recorrido dentro de uno de los clusters de F1, que genera un nuevo buffer simulando la cinta de F, y se la env´ıa a F2.F2, por su parte, reenv´ıa el buffer a F1para que pueda efectuar la siguiente transici´on. Es importante hacer hincapi´e en el inicio de todo este procedimiento: al principio, el input de Fse pone en el buffer B1(sin ninguna modificaci´on), y el estado inicial de F1es q# 0(recordemos que el estado inicial de Fera q0). As´ı, lo primero que har´a F1ser´a generar una #, lo cual le ayudar´a a distinguir ese buffer del que se corresponder´a al siguiente estado de la cinta de F. Despu´es seguir´a tratando los literales de B1con total normalidad, empezando en el cluster de q0, claro. Y simular el criterio de aceptaci´on de Ftambi´en es sencillo: simplemente tenemos que hacer que (qi, q)∈Q1×Q2sea de aceptaci´on siempre que qirepresente en F1 un estado final de F, es decir, qi∈QF⊆Q. De esta forma, hemos hecho una reducci´on del LBA Fa un sistema de FSMs en el cual los outputs no proliferan, como hemos comprobado a la hora de construirlos. Adem´as, en el sistema de FSMs que hemos construido, el n´umero de estados es polin´omico con respecto a los de F: |QF1|= #clusters ·#estados por cluster ≤ |QF|·(|QF|+ 1) ·(|ΣF|+ 1) + 1 + |ΣF|+ 1∈ O|QF|2 Esto demuestra que la creaci´on del sistema de FSMs en funci´on de Fse puede hacer con una cantidad de estados polin´omica respecto al tama˜no de F. Adem´as, la reducci´on, en cuanto a tiempos de ejecuci´on, tambi´en es polin´omica: si tenemos un input de longitud ny, para procesar dicho input, Fda kpasos; entonces nuestro sistema S, por cada uno de estos kpasos recorrer´a la cinta entera de Fdos veces (una ser´a por un recorrido de F1y otra por el de F2). Pero como Fes un LBA, el tama˜no de la cinta siempre est´a acotado por n. Es decir, el sistema Sdar´a O(nk) pasos en su ejecuci´on. Por tanto, podemos afirmar que la reducci´on es polin´omica y no se a˜nade por tanto un sobrecoste rese˜nable. Cap´ıtulo 7 Sistemas con buffers acotados Otro caso que podemos estudiar es el de un sistema de FSMs en comunicaci´on en el cual los buffers, por alguna raz´on, tienen tama˜no acotado desde el principio, como definimos en el apartado 5.1. Esto supone una limitaci´on similar a la estudiada en el caso de que los outputs no proliferaran en el sentido de que estamos limitando la expresividad de nuestro sistema. En el caso de que los outputs no proliferaran ya estudiamos que el sistema dejaba de ser Turing completo, y se quedaba en un estadio un poco anterior de la jerarqu´ıa de Chomsky, el de los lenguajes dependientes del contexto. En este caso, vamos a ver sin mucha dificultad que podemos comprobar que la limitaci´on de la expresividad es mucho m´as potente, y este tipo de sistemas se van a quedar en lo m´as bajo de la jerarqu´ıa, en los lenguajes regulares. Esto se debe a que la informaci´on que potencialmente puede tener el sistema es en cualquier caso finita, pues las FSMs involucradas lo son, y los buffers tambi´en. Esto contrasta con el caso anterior por una sutileza: cuando no proliferaban los outputs, la informaci´on estaba acotada dependiendo del tama˜no inicial del input, pero como el tama˜no inicial del input no est´a acotado de antemano, la cantidad de informaci´on que ten´ıan esos sistemas es mucho mayor que la de los sistemas que pasamos a estudiar ahora. Vamos a proceder a simular un sistema de FSMs con buffers acotados mediante un aut´omata finito. Esto demostrar´ıa que nuestro sistema de FSMs como mucho puede reconocer lenguajes regulares. Pero como, en concreto, el sistema est´a formado por FSMs, que son aut´omatas finitos, tambi´en el sistema puede simular cualquier aut´omata finito, y esto demuestra la equivalencia entre ambos modelos. La conclusi´on clara es que a˜nadir buffers acotados a unas FSMs para que se comuniquen entre ellas no a˜nade en ning´un caso expresividad. Teorema 7.1. Cualquier sistema de FSMs en comunicaci´on con buffers acotados puede ser simulado por un aut´omata finito. Demostraci´on. Sea S= (F0, F1, F2, . . . , Fn) un sistema de FSMs en comunicaci´on con buffers acotados, con buffers B0, B1, B2, . . . , Bn. Recordemos que esto significa que existe un Mprefijado de forma que la longitud de todos los buffers (excepto B0, que corresponde a la m´aquina especial F0seg´un definimos en la secci´on 5.1) est´a siempre acotada por M. Digamos que el alfabeto com´un de Ses Σ, y con ´el definimos Σ≤M:= {w∈Σ∗:|w| ≤ M}, que nos ayudar´a a simplificar las expresiones relativas a los buffers. Adem´as, las m´aquinas ser´an Fi= (Qi, Ii, Oi, q0 i, δi), con 0 ≤i≤n, y Ii, Oi⊆Σ, naturalmente. Definamos ahora el aut´omata finito F= (Q, Σ, q0, QF, δ) que los simular´a. La clave est´a en hacer Q=Q1×Σ≤M×Q2×Σ≤M× ··· × Qn×Σ≤M, que 32 Cap´ıtulo 7 - Sistemas con buffers acotados 33 simular´a por completo el estado del sistema Sde la siguiente forma: el estado (q1, α1, q2, α2, . . . , qn, αn)∈Qsimbolizar´a que F1est´a en el estado q1,F2, en q2, y as´ı sucesivamente; y que el buffer B1tiene por contenido la palabra α1,B2tiene la palabra α2, y as´ı sucesivamente. Notemos que algunas de las posiciones de los buffers pueden estar vac´ıas, pues no necesariamente |αi|=M, sino que en general tendremos |αi| ≤ Mpor ser palabras de Σ≤M. Como vemos, el alfabeto ser´a Σ, el mismo que ten´ıa S, lo cual es necesario para que Fpueda aceptar los mismos s´ımbolos. Para cada s´ımbolo γ∈Σ que marque una transici´on de F, querremos que signifique que la m´aquina F0introduce en ese instante el siguiente literal del input inicial, que esta vez ser´a γ, dej´andolo en el final del buffer B1, claro. Pero en cada estado de Fhabr´a m´as transiciones: aquellas que pueda dar el sistema Ssin consumir literales del input (y por eso Fconsumir´a ´unicamente ), y que reflejan que una m´aquina Fi, con i≥1, ha dado un paso en su ejecuci´on. Nos falta definir la funci´on de transici´on δde F, lo cual es sencillo a partir de las ideas anteriores. Tenemos que entender c´omo reacciona ante los diferentes literales de Σ, as´ı que pasamos a definir estas transiciones. Supongamos que estamos en un estado arbitrario (q1, α1, q2, α2, . . . , qn, αn)∈Q. Veamos cu´ales son las diferentes transiciones que tiene este estado en F. Para los literales γ∈Σ, tenemos que a˜nadir γaB1en caso de que este buffer no est´e lleno. |α1|< M =⇒δ((q1, α1, q2, α2, . . . , qn, αn), γ)=(q1, α1+γ, q2, α2, . . . , qn, αn) Para las transiciones que se toman con , tenemos que simular una transici´on de la m´aquina Fi, para cada 1 ≤i≤n. Esta transici´on depender´a de head(αi) (en caso de que el buffer Bino est´e vac´ıo). Digamos que la transici´on es la siguiente: δi(qi, head(αi)) = (q0 i, β1, β2, . . . , βn), donde q0 i∈Qies el estado de llegada y βj∈Σ?es lo que se a˜nade a Bjpara 1 ≤j≤n(recordemos que F0no participa en la comunicaci´on, as´ı que por simplicidad la omitimos). La transici´on ser´a posible en caso de que ninguno de los buffers exceda su tama˜no al a˜nadir estos literales, lo cual podemos expresar de la siguiente forma: |αi|>0∧αi=X+α0 i ∧δi(qi, X)=(q0 i,β1, β2, . . . , βn) ∧ |αj+βj| ≤ M∀1≤j≤n con i 6=j=⇒ (q1, α1+β1, q2, α2+β2, . . . , q0 i, α0 i+βi, . . . , qn, αn+βn) ∈δ((q1, α1, q2, α2, . . . , qi, αi, . . . , qn, αn), ) Por ´ultimo, comentar el estado inicial de la m´aquina F. Simplemente ser´ıa el estado (q0 1, , q0 2, , . . . , q0 n, ). Y naturalmente, los estados de aceptaci´on de Fser´an aquellos en los cuales (q1, q2, . . . , qn) sea una configuraci´on de aceptaci´on de S. Con este sencillo procedimiento queda claro que el aut´omata F(finito) que hemos definido simula el comportamiento de S, pues simula cada uno de los pasos que puede tomar en cada una de sus configuraciones. Cap´ıtulo 7 - Sistemas con buffers acotados 34 Adem´as la reducci´on es polin´omica conforme crece el tama˜no de las m´aquinas del sistema S: si Stiene kestados (es decir, |Q1|+|Q2|+. . . +|Qn|=k), entonces Ftiene, a lo sumo, con una aproximaci´on na¨ıve, (kM)nestados, lo cual es una cantidad polin´omica en k, supuesto que el n´umero nde m´aquinas que conforman S y la constante que acota los buffers Mson conocidas de antemano. Cap´ıtulo 8 Sistemas con buffers sin orden Otra modificaci´on posible de los sistemas de FSMs en comunicaci´on residir´ıa en modificar el funcionamiento de los buffers. Hasta ahora, siempre han estado implementados en forma de cola, de forma que los literales siempre quedaban ordenados conforme a su momento de llegada. Ahora vamos a estudiar la situaci´on en la cual este orden se perdiera, por ejemplo por las caracter´ısticas f´ısicas de nuestro sistema, que podr´ıa no soportar estructuras de tipo cola o simplemente estructuras ordenadas, o porque el protocolo usado no permite asegurar que se respete el orden de llegada a los buffers. Se nos plantea entonces la siguiente modificaci´on: si el contenido de los buffers puede ser representado por multiconjuntos en lugar de colas, es decir, estos buffers pertenecen a Σ⊕(recordemos que X⊕es la clase de multiconjuntos finitos con elementos en X) en vez de a Σ∗(donde Σ es el alfabeto del sistema), ¿qu´e caracter´ısticas tienen estos sistemas? Lo primero que vamos a hacer es definir c´omo evolucionan este tipo de sistemas, pues las reglas que definimos en la secci´on 5no funcionan. Sin embargo, una ligera modificaci´on de c´omo se comportan las funciones de transici´on que hab´ıamos estudiado anteriormente nos proporciona un marco para este tipo de sistemas. Definici´on 8.1. Decimos que S= (F1, F2, . . . , Fn)es un sistema de FSMs en comunicaci´on sin orden en el caso de que las distintas FSMs generan outputs en Σ⊕(en vez de en Σ∗, como era habitual), es decir, δi:Qi×Σ?−→ Qi×(Σ⊕)n para 1≤i≤n. Una configuraci´on de Sser´a una tupla de Q1×Σ⊕×Q2×Σ⊕× ···×Qn×Σ⊕. La funci´on de transici´on entre distintas configuraciones de Ses δ:Q1×Σ⊕× Q2×Σ⊕×···×Qn×Σ⊕−→ Q1×Σ⊕×Q2×Σ⊕×···×Qn×Σ⊕, que viene definida de la siguiente manera: contains(Bi, γ)∧δi(qi, γ)=(q0 i, α1, α2, . . . , αn) =⇒ (q1, B1+α1, . . . , qi−1, Bi−1+αi−1, q0 i, erase(Bi, γ) + αi, qi+1, Bi+1 +αi+1, . . . , qn, Bn+αn) ∈δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn) En este caso contains(B, γ) es una funci´on que dice si hay alguna ocurrencia del literal γ∈Σ en el multiconjunto B(trivialmente cierto si γ=), erase(B, γ) es una funci´on que elimina una ocurrencia de γde B(lo cual podr´ıamos entender como B\{γ}), y + representa la suma usual de multiconjuntos (si un literal γaparece a veces en el multiconjunto Aybveces en B, entonces aparece a+bveces en A+B). 35 Cap´ıtulo 8 - Sistemas con buffers sin orden 36 Como hasta ahora, las configuraciones dependen de los estados en que est´an las diferentes FSMs en cada instante, y los multiconjuntos se pueden interpretar como el contenido de los buffers B1, B2, . . . , Bn, que esta vez funcionan como multiconjuntos. La m´aquina Fitoma inputs de Biy genera outputs que se a˜naden al resto de buffers. Una vez vista la adaptaci´on de la definici´on de sistemas de FSMs en comunicaci´on a esta situaci´on, vamos a establecer una comparativa con las redes de Petri, pues son los sistemas m´as conocidos que trabajan con multiconjuntos, es decir, con inputs y outputs sin un orden definido. 8.1. Expresividad de los sistemas con buffers sin orden Lo primero que vamos a hacer es comprobar que estos sistemas son en realidad simulables por redes de Petri usuales. Vamos a recordar este concepto: Definici´on 8.2. Una red de Petri Nes una tupla (P, T, A, M, W).Pes el conjunto de lugares de N,Tel conjunto de transiciones y A⊆(P×T)∪(T×P)el conjunto de arcos (o relaci´on de flujo entre lugares y transiciones). En cada momento, cada lugar de Ptiene una cantidad no negativa de tokens, indicada por el marcaje M:P−→ N. Y cada transici´on de Tpuede consumir o generar una cantidad distinta de tokens en cada uno de los lugares que se relacionan con ella a trav´es de los arcos de A. La cantidad de tokens que se intercambian con cada transici´on por medio de cada arco vienen determinados por W:A−→ N. A la vista de la definici´on, veamos el resultado que augur´abamos. Proposici´on 8.3. Cualquier sistema de FSMs en comunicaci´on con buffers sin orden puede ser simulado por una red de Petri. Demostraci´on. Dado un sistema S= (F1, F2, . . . , Fn), vamos a construir una red de Petri Nque lo simule. La red de Petri ser´a N= (P, T, A, M, W), como en la definici´on anterior. Supongamos que el alfabeto de Ses Σ. Por cada estado qide cada m´aquina Fjtendremos un lugar en P, que denotaremos qj i. Estos lugares tendr´an siempre a lo sumo un token, y representar´an si la m´aquina Fjest´a en el estado qia lo largo de la simulaci´on que hace N. Adem´as, por cada literal γ∈Σ y cada buffer Bjtendremos tambi´en un lugar, bj γ, que tendr´a tantos tokens como ocurrencias de γhaya en Bjen un instante determinado. En principio, por las caracter´ısticas de los sistemas de FSMs, estos lugares no est´an acotados. Por cada transici´on de Fj, 1 ≤j≤n, tendremos una transici´on en N. Es decir, si numeramos las transiciones de cada m´aquina Fjdesde el 1 hasta rj, el conjunto de transiciones de Nser´a T={tj i: 1 ≤j≤n, 1≤i≤rj}, donde tj isimular´a la i-´esima entrada de δj. Queda por tanto definir las relaciones entre lugares y transiciones, a trav´es de relaci´on de flujo A. Supongamos que tenemos una transici´on arbitraria de δj, digamos Cap´ıtulo 9 Sistemas de Mensajes Perdidos En nuestro camino explorando diferentes versiones de nuestros sistemas de FSMs podemos visitar uno de los modelos m´as conocidos y estudiados de este tipo. Si suponemos que los canales de comunicaci´on que usamos (los buffers que ayudan a la comunicaci´on en nuestro caso) no son ideales y, por tanto, son susceptibles a fallos de forma que algunos literales puedan desaparecer de ellos en cualquier momento sin ning´un mecanismo que controle estas p´erdidas, llegamos a un concepto bastante similar al de los Sistemas de Mensajes Perdidos (LCS por su nombre en ingl´es: Lossy Channel Systems). Los LCS usuales que podemos encontrar en la literatura son un tipo de sistemas de FSMs en comunicaci´on en los cuales hay un tipo de transici´on adicional: en cualquier punto de la ejecuci´on, pueden desaparecer un conjunto de literales de cualquier buffer del sistema. Este comportamiento es puramente no determinista: no hay manera de controlarlo, puede surgir en cualquier momento y afectar a cualquier grupo de literales. Dado este no determinismo inherente a los LCS, en general se suele permitir tambi´en que las FSMs utilizadas sean no deterministas (y recordemos que no toda FSM no determinista se puede convertir en una determinista, pues ante una misma secuencia de inputs las FSMs no deterministas pueden generar potencialmente m´as cadenas de outputs diferentes que las deterministas), lo cual los diferencia un poco m´as de nuestros sistemas de FSMs. En general, un LCS puede, en cierto sentido, simular las ejecuciones de un sistema de FSMs, pues una de sus posibles ejecuciones es aquella en la que las transiciones que pierden literales nunca se activan, y en concreto este ser´ıa el comportamiento que tienen nuestros sistemas. No obstante, las propiedades de ambos tipos de sistemas no son las mismas porque en los LCS hay muchas m´as posibles ejecuciones en las que se pierden algunos literales de los buffers. En cambio, una simulaci´on en sentido contrario no es posible a menos que introduzcamos cambios en la definici´on de nuestros sistemas (no es posible simular esas p´erdidas de literales no deterministas con nuestros sistemas de FSMs usuales), pues hay propiedades en las que ambos modelos difieren: por ejemplo, el problema de la terminaci´on (que el sistema no tenga ramas de ejecuci´on infinitas dado un input) es decidible en el caso de los LCS e indecidible en el de los sistemas de FSMs en comunicaci´on (Problema de Parada). Una forma de hacer que nuestros sistemas de FSMs pudieran tener la capacidad de perder mensajes de forma no determinista, como ocurre en los LCS, ser´ıa introducir un cierto grado de no determinismo en las FSMs. Por ejemplo, si para cada transici´on δ(q, α)=(q0, β) de una de las FSMs de nuestro sistema permitimos a˜nadir tambi´en la transici´on δ(q, α)=(q0, ), estar´ıamos pudiendo simular este 43 Cap´ıtulo 9 - Sistemas de Mensajes Perdidos 44 fen´omeno ya que, de manera no determinista, podr´ıan no llegar los mensajes a su buffer destino. Adem´as, esto es introducir un no determinismo muy controlado, as´ı que tampoco es que el cambio haya sido excesivo. Lo interesante va a ser la diferencia entre propiedades que generan estos cambios. Aunque pueda parecer algo parad´ojico, numerosos problemas de decisi´on son m´as tratables en los LCS que en el caso de los sistemas de FSMs en comunicaci´on y las m´aquinas de Turing, donde esencialmente los problemas son indecidibles en su mayor´ıa. En concreto, un problema de vital importancia, como es el de la alcanzabilidad, es decidible para los LCS ([2], cap´ıtulo 5) . Tambi´en es decidible el problema de la inevitabilidad (dado un conjunto de estados, ¿es inevitable que cualquier ejecuci´on maximal pase por alguno de dichos estados?), que engloba el problema de la terminaci´on (usando como conjunto de estados aquellos estados en los cuales la ejecuci´on termina), muy importante tambi´en en la teor´ıa de aut´omatas ([21], teorema 8). Tambi´en son decidibles otras propiedades que comprueban que a lo largo de las ejecuciones maximales se conservan ciertas propiedades, lo cual es de utilidad en este caso debido a que es importante tener ciertos m´etodos de verificaci´on del funcionamiento de los sistemas que palien en cierto modo su naturaleza, que permite que los mensajes se pierdan. No obstante, ni mucho menos todas las propiedades de estos sistemas son decidibles: en general, otras como la acotaci´on (¿la cantidad de literales que puede haber en un canal/buffer a lo largo de cualquier ejecuci´on est´a acotada?) o ciertas propiedades de justicia, como saber si es inevitable pasar por un cierto estado de control infinitas veces, son indecidibles ([1], teorema 3.7). M´as a´un: a pesar de ser decidibles los problemas antes comentados, como el de la alcanzabilidad, tienen una complejidad extremadamente grande. No est´an asociados a funciones recursivas primitivas ([27], teoremas 4.2, 4.4). De hecho, se puede ver la gran distancia a la que est´an de esta clase de funciones con un breve vistazo a la Jerarqu´ıa de Crecimiento R´apido (Fast Growing Hierarchy): las funciones recursivas primitivas est´an asociadas a ordinales acotados superiormente por ω(el primer ordinal numerable), mientras que los problemas de la alcanzabilidad e inevitabilidad est´an asociados al ordinal ωω. 9.1. Introduciendo justicia en las ejecuciones Una vez vistas las propiedades b´asicas de los LCS en general, vamos a comprobar que introducir a nuestros sistemas de FSMs la capacidad de hacer que los mensajes se puedan perder de forma no determinista hace que consigamos una clase restringida de los LCS generales, y esto nos va a proporcionar alguna ventaja interesante. Por ejemplo, ser´ıa interesante introducir ciertas nociones de justicia en este tipo de sistemas. Esto se debe a que el hecho de que los mensajes se puedan perder puede llegar a degradar bastante la comunicaci´on entre varias m´aquinas en una situaci´on real, en la cual podr´ıa ser que la red fallara mucho y casi ning´un mensaje se mandara. Si tuvi´eramos asegurada cierta justicia en nuestro ambiente, como que ciertos comportamientos se tienen que dar peri´odicamente sean cuales sean las circunstancias, Cap´ıtulo 9 - Sistemas de Mensajes Perdidos 45 podr´ıamos al menos intentar paliar los posibles fallos de la red repitiendo el env´ıo de los mensajes, pues la justicia nos asegurar´ıa que, tarde o temprano, es seguro que los mensajes llegar´an. Dos modelos de justicia interesantes que van a ser de especial inter´es son los que se estudian en [20]. Para un sistema S= (F1, . . . , Fn): Decimos que una ejecuci´on es d´ebilmente justa si para cada m´aquina Fise cumple que est´a bloqueada (es decir, que dada la composici´on de su buffer y su estado actual, no puede avanzar en ese instante) un n´umero infinito de veces a lo largo de la ejecuci´on o que infinitos pasos de la ejecuci´on de Sson pasos de Fien los que desaparecen literales de su buffer. Decimos que una ejecuci´on es fuertemente justa si para cada m´aquina Fise cumple que a partir de un cierto paso de la ejecuci´on de SFiest´a siempre bloqueada o si infinitos pasos de la ejecuci´on de Sson pasos de Fien los que desaparecen literales de su buffer. Ambos conceptos b´asicamente de lo que nos est´an informando es de que, mientras no est´an bloqueadas, las m´aquinas van altern´andose relativamente entre ellas en su ejecuci´on, hay una cierta justicia entre todas las m´aquinas. En la justicia fuerte adem´as se exige que cada m´aquina no se bloquee casi nunca o que termine en tiempo finito su ejecuci´on, lo cual da la idea de que, entre aquellas m´aquinas que no se bloqueen en tiempo finito, tendr´a que haber gran grado de alternancia en las ejecuciones. Adem´as, l´ogicamente, si una ejecuci´on es fuertemente justa, tambi´en es d´ebilmente justa. Veamos ahora qu´e pasa si imponemos estos sentidos de justicia a la modificaci´on de los sistemas de FSMs en comunicaci´on en los cuales permitimos que se pierdan mensajes. Estudiaremos qu´e pasa con el problema de la terminaci´on imponiendo estos conceptos de justicia: ¿todas las ramas de ejecuci´on de nuestro sistema acaban en tiempo finito imponiendo justicia fuerte/d´ebil? La respuesta es la contraria a ¿hay alguna ejecuci´on infinita en la que se respete la justicia fuerte/d´ebil?, que tambi´en puede servir en ocasiones para diferentes interpretaciones. F1 F2 ··· Fn Buffer 1 Buffer 2 ··· Buffer n Figura 9.1: Esquema de las comunicaciones en un sistema de FSMs en comunicaci´on. Lo que podemos ver es que, por la forma en que hemos dise˜nado nuestros sistemas de FSMs, cada buffer solo sirve como input de una ´unica m´aquina (lo cual podemos ver gr´aficamente en la figura 9.1). Esto hace que tengamos una clase restringida de los LCS, que en [20] llaman sistemas sin canales multiplexados. Esto es interesante porque en LCS generales se tiene el siguiente resultado: Cap´ıtulo 9 - Sistemas de Mensajes Perdidos 46 Proposici´on 9.1 (3.1 en [20]).En LCS sin canales multiplexados el problema de la terminaci´on imponiendo justicia fuerte/d´ebil es decidible. Por tanto, en el caso de nuestros sistemas de FSMs modificados, como acabamos de ver en los p´arrafos anteriores, est´an contenidos en la subclase de los LCS sin canales multiplexados, podemos aplicarles el teorema 9.1 (sabiendo que, como es sencillo comprobar, ser decidible es una propiedad que las subclases heredan). Esto nos conduce al siguiente resultado: Corolario 9.2. En los sistemas de FSMs en comunicaci´on modificados para que se puedan perder mensajes de los buffers de manera no determinista, el problema de la terminaci´on es decidible si imponemos justicia fuerte o d´ebil. Esta propiedad es interesante porque nos informa de que podemos introducir conceptos de justicia a bajo coste (sin perder la decibilidad de la propiedad de terminaci´on). Y es interesante introducir la justicia porque as´ı tenemos algunas certezas m´as que en el caso de que no tengamos absolutamente ning´un control sobre la p´erdida de mensajes en nuestro sistema. Cap´ıtulo 10 Complejidad de algunas propiedades A pesar de que, en virtud del teorema de Rice, todos los problemas de decisi´on no triviales sobre sistemas de FSMs en comunicaci´on son indecidibles (pues lo son para las m´aquinas de Turing), podemos estudiar la complejidad de resolver alguno de estos problemas en algunas de sus versiones simplificadas que s´ı queden en el rango de lo decidible. 10.1. El problema de la alcanzabilidad finita En este apartado vamos a entrar m´as a fondo en una de las propiedades b´asicas: la alcanzabilidad. Como el problema de la alcanzabilidad, en su versi´on general, resulta indecidible, en este caso estudiaremos la alcanzabilidad finita (que aqu´ı denotaremos tambi´en N-alcanzabilidad, para que quede claro que la limitaci´on de la finitud viene prefijada por una constante N), que es el siguiente problema: dado un natural N y una posible configuraci´on de nuestro sistema de FSMs en comunicaci´on S, ¿es posible alcanzar dicha configuraci´on dando Sa lo sumo Npasos en su ejecuci´on? De hecho, veremos el caso de que la configuraci´on que buscamos alcanzar sea una cualquiera en la que Sacepta, plante´andonos el problema ¿puede aceptar Sen a lo sumo Npasos en su ejecuci´on? Veremos que este problema de decisi´on no es sencillo de resolver en el caso general, tanto que resulta ser un problema NP-completo. Vamos a proceder a la demostraci´on de este hecho. Lema 10.1. El problema de la alcanzabilidad finita en sistemas de FSMs en comunicaci´on es NP. Demostraci´on. Si tenemos un sistema de FSMs en comunicaci´on S= (F1, F2, . . . , Fn), saber si Salcanzar´a un determinado estado en menos de Npasos es un problema NP: de manera no determinista se puede, en caso de que haya forma de alcanzar dicho estado, acertar cu´al es el orden de ejecuci´on, es decir, si el siguiente paso del sistema ser´a ejecutar una transici´on de F1, de F2. . . o de Fn. Dado este orden de ejecuci´on, es ya trivial comprobar que funciona: simplemente vamos ejecutando las transiciones en F1, F2, . . . , Fny modificando los buffers correspondientes, y al final comprobamos si el estado al que hemos llegado es el esperado. Esta comprobaci´on es claramente polin´omica, de hecho O(N) si implementamos convenientemente las operaciones de inserci´on y extracci´on de elementos de los buffers. 47 Cap´ıtulo 10 - Complejidad de algunas propiedades 48 Hay que tener en cuenta que para que esto sea realmente un comportamiento polin´omico, Ntiene que haber sido recibido como input en base unaria, es decir, el input Nse representa recibiendo Ntokens del mismo tipo. Notemos que es importante porque si nos dieran Ncomo input en binario, por ejemplo, O(N) ser´ıa un tiempo exponencial en el tama˜no del input. Pero es una hip´otesis razonable trabajar en base unaria en este tipo de situaciones porque si no, incluso el simple problema de que un aut´omata d´e Npasos tarda un tiempo exponencial en ejecutarse; mientras que considerando la base unaria, es como si nuestro aut´omata fuera consumiendo tokens con cada paso que da y el comportamiento ser´ıa polin´omico, lo cual resulta bastante m´as razonable. Ahora querr´ıamos demostrar la NP-completitud del problema de la N-alcanzabilidad en estos sistemas: para ello, vamos a reducir el problema del 3-SAT (del cual es bien conocida su NP-completitud) al de la N-alcanzabilidad de uno de estos sistemas. Describamos esta reducci´on en detalle. Teorema 10.2. El problema de la alcanzabilidad finita en sistemas de FSMs en comunicaci´on es NP-completo. Demostraci´on. Supongamos que tenemos como input una f´ormula de 3-SAT φ con nvariables, y queremos decidir si φes o no satisfactible (es decir, resolver el problema del 3-SAT) usando un sistema de FSMs. Vamos a crear un sistema Sde FSMs en comunicaci´on con varias m´aquinas (donde no todas las m´aquinas se comunicar´an con todas las restantes). Dos de ellas ser´an F1, F2:F1tiene un ´unico estado en el cual devuelve 0 ante cualquier input (y permanece en ese estado); mientras que F2tiene, de nuevo, un ´unico estado (donde siempre permanece) en el cual devuelve esta vez un 1 ante cualquier input. De esta forma, fruto del no determinismo de las comunicaciones de F1, F2, podr´ıamos generar cualquier cadena compuesta por ceros y unos, lo cual vamos a utilizar con m´as m´aquinas. Los outputs tanto de F1como de F2ir´an ´unicamente a la m´aquina F3, que posteriormente definiremos. q1 0/0 Figura 10.1: Esquema gr´afico de F1. q2 0/1 Figura 10.2: Esquema gr´afico de F2. Usaremos tambi´en un checker de f´ormulas de 3-SAT, que funcionar´a de la siguiente forma: como la f´ormula φ, que este checker recibir´a como input, tiene n variables (que podemos suponer ordenadas de alg´un modo), el checker usar´a los nprimeros inputs que le lleguen (en este caso de F1yF2, como veremos) para asign´arselos como valores de las variables de φ, en ese mismo orden. Una vez le lleguen esos primeros ninputs, podr´a comprobar si esos valores satisfacen φ, y generar una respuesta afirmativa o negativa. Este checker se puede construir de manera sencilla como m´aquina de Turing. Y como vimos en el apartado 4.2, los sistemas de FSMs en comunicaci´on con 2 FSMs son una clase Turing completa, as´ı que este checker puede ser implementado mediante 2 FSMs en comunicaci´on, digamos F4, F5. Adem´as, el checker puede ser implementado sencillamente de forma que se ejecute Cap´ıtulo 10 - Complejidad de algunas propiedades 49 en tiempo lineal con respecto a los inputs de las f´ormulas que recibe. Y, como vimos en el apartado 4.2, la transformaci´on de m´aquinas de Turing a sistemas de FSMs en comunicaci´on era suficientemente buena como para poder afirmar que solo a˜nad´ıamos una cantidad polin´omica de sobrecoste. Por tanto, podemos afirmar que el comportamiento del checker implementado con F4, F5ser´a polin´omico en el n´umero de literales de la f´ormula φque nos den como input. Para comunicar las m´aquinas F1, F2con este checker (F4, F5), usaremos una sencilla m´aquina F3intermediaria: recibir´a los outputs que F1yF2generen, y los dejar´a pasar (en un ´unico canal), ´unicamente, hacia el checker, en el orden que le lleguen. De esta forma conseguimos simplificar la forma en que llegan los ceros y unos generados por F1, F2al checker. q3 0 0/0 1/1 Figura 10.3: Esquema gr´afico de F3. Y por ´ultimo tenemos una m´aquina F6que lo ´unico que hace es esperar la respuesta del checker. Cuando F4yF5hayan procesado suficiente informaci´on como para saber si la f´ormula φes o no satisfactible, enviar´an un mensaje (afirmativo o negativo en cada caso, digamos que mediante los literales >,⊥) a F6. La recepci´on de un mensaje afirmativo har´a que F6transite a un estado diferente q6 f, que ser´a el ´unico estado de aceptaci´on de S, o sea, que las ´unicas configuraciones de Sde aceptaci´on son aquellas en las que F6est´a en q6 f(reduciendo as´ı el problema a una especie de alcanzabilidad finita de F6dentro del sistema S). Y el problema de la N-alcanzabilidad de Sen este caso lo plantearemos en este caso, como explic´abamos al inicio, como ¿alcanza Ssu configuraci´on de aceptaci´on en menos de Npasos de S? q6 0q6 f >/ x/ (x6=>) Figura 10.4: Esquema gr´afico de F6. Con esto ya tendr´ıamos nuestro sistema S= (F1, F2, F3, F4, F5, F6) construido, de forma que las diferentes m´aquinas se comunican ´unicamente con las que muestra el diagrama de la figura 10.5. Veamos ahora por qu´e funciona realmente esta reducci´on. Cap´ıtulo 10 - Complejidad de algunas propiedades 50 F1 F2 F3checker (F4+F5) input (φ) F6 Figura 10.5: Diagrama explicativo de las comunicaciones que se establecen en S. Dada la construcci´on anterior, al checker le llegar´an ceros o unos en funci´on de qu´e m´aquina ejecute el siguiente paso de entre F1, F2. Supongamos que el checker formado por F4, F5tiene que ejecutar p(|φ|) pasos para poder decidir si la f´ormula φ(denotamos por |φ|el tama˜no de la f´ormula φcomo input, y recordamos que tiene n≤ |φ|variables) es o no satisfactible. Por la discusi´on anterior, pes un polinomio. Entonces, en caso de que φsea satisfactible, definiendo N:= p(|φ|) + 2n+ 1 ≤ p(|φ|)+2|φ|+1, es claro que en Npasos Spodr´a llegar a su estado de aceptaci´on, es decir, aquel en el que F6est´a en q6 f(p(|φ|) pasos ser´an del checker, nde las m´aquinas F1, F2para generar los literales que hacen φcierta, nde F3para dejar pasar estos literales por un mismo canal y 1 final de la respuesta que el checker env´ıa a F6). Y, ciertamente, el rec´ıproco tambi´en es cierto: si la f´ormula φno es satisfactible, en ninguna ejecuci´on de Sde longitud Nel sistema podr´a llegar a su estado de aceptaci´on. Por tanto, podemos concluir que la reducci´on del problema de la satisfactibilidad de φ, una f´ormula cualquier de 3-SAT , ha sido reducida a un problema de N-alcanzabilidad en sistemas de FSMs en comunicaci´on. Adem´as, la reducci´on es polin´omica porque la construcci´on de Ses polin´omica respecto al tama˜no de φ(pues la construcci´on de cada m´aquina es en verdad independiente de φ, as´ı que podemos considerar que la construcci´on de Ses O(1) en cuanto a n´umero de estados, y lineal en cuanto a tama˜no de los buffers, pues el checker recibe el input completo y ninguna m´aquina m´as tiene literales en su buffer inicialmente), y Ntambi´en lo es. De esta forma, estamos ya en posici´on de afirmar que el problema de la Nalcanzabilidad en sistemas de FSMs es en efecto NP-completo, como quer´ıamos demostrar. De hecho, que el problema sea NP-completo no deber´ıa resultarnos una gran sorpresa en realidad, pues el alt´ısimo grado de no determinismo que tienen los sistemas de FSMs en sus comunicaciones hace pr´acticamente imposible conseguir que pasen a la frontera de lo polin´omico. De hecho, incluso con ´unicamente 2 m´aquinas, como hac´ıamos en la demostraci´on anterior con F1yF2, el intercalado que puede existir entre sus ejecuciones hace que el n´umero de posibles cadenas de ceros y unos que le puedan llegar a la F3anterior crezca exponencialmente conforme a los pasos Cap´ıtulo 10 - Complejidad de algunas propiedades 51 que ejecutan F1yF2. Si dejamos que a F3le lleguen nliterales, habr´a 2ncadenas posibles que le puedan llegar, un crecimiento claramente exponencial. Pero resulta m´as interesante comprobar que aunque limitemos la capacidad de intercalado de F1yF2, vuelven a generarse una cantidad exponencial de cadenas. Esto lo podemos comprobar imponiendo unas ciertas condiciones de justicia en estas comunicaciones. Por ejemplo, si no dejamos que una m´aquina ejecute m´as de k(≥2) pasos seguidos, podr´ıamos esperar que disminuyera bastante el n´umero de cadenas posibles que se pueden generar. Pero resulta que sigue siendo exponencial, pues la cantidad de cadenas de longitud nque se podr´an generar cumple la recurrencia cn=cn−1+cn−2+. . . +cn−k, una de las llamadas sucesiones de Fibonacci generalizadas, que tienen car´acter exponencial, con bases comprendidas entre ϕ≈1,6180 . . . y 2 ([28], lema 3.6). Si limitamos que las 2 m´aquinas no puedan ejecutar kpasos consecutivos, obtenemos un resultado similar. El caso m´as fuerte en este sentido ser´ıa uno en el cual implement´aramos una justicia tal que solo permiti´eramos ejecuciones intercaladas de F1yF2, de forma que, de alguna forma, pudi´eramos dividir cada cadena recibida por F3en grupos de dos literales que podr´ıan ser ´unicamente 01 o 10. Igualmente, en este caso cn≈ 2n/2=√2n, que seguir´ıa siendo exponencial. De esta forma vemos que, a´un limitando artificialmente la capacidad de comunicaci´on de las distintas m´aquinas mediante diferentes tipos de justicia, continuamos obteniendo cantidades no polin´omicas de posibles ejecuciones, lo cual nos indica que pod´ıamos esperar el resultado que hemos dado en este cap´ıtulo. 10.1.1. En sistemas con buffers acotados A modo de comparativa podemos considerar el problema de la alcanzabilidad finita en el caso de sistemas de FSMs en comunicaci´on con buffers acotados, tal y como definimos en el apartado 5.1. En este caso, y en el mismo esp´ıritu que obten´ıamos que su expresividad era bastante limitada, pues son tan expresivos como los aut´omatas finitos (como vimos en 7.1), vamos a conseguir ver que el problema de la N-alcanzabilidad es mucho m´as sencillo de resolver, pues es polin´omico en N. Lema 10.3. El problema de la alcanzabilidad finita en sistemas de FSMs en comunicaci´on con buffers acotados es polin´omico (P). Demostraci´on. Dado un sistema Sde FSMs en comunicaci´on con buffers acotados, podemos conseguir un aut´omata finito Fequivalente, cuyo tama˜no no depende de Ny es polin´omico en el tama˜no de S, como vimos al final del cap´ıtulo 7. Y la construcci´on del grafo de alcanzabilidad de Fhasta llegar a profundidad N(pues m´as all´a no vamos a obtener respuestas al problema de la N-alcanzabilidad, as´ı que no lo necesitamos) es O(N): en efecto, a cualquier profundidad d,Fsolo podr´a estar en una cantidad O(1) de estados, pues son los que resultan de considerar los estados de F(constantes respecto a Npor la discusi´on anterior); y para construir el siguiente nivel del grafo (profundidad d+ 1) necesitamos solo considerar los estados Cap´ıtulo 10 - Complejidad de algunas propiedades 52 del nivel d. Por tanto, cada nivel se crea en tiempo constante, y de ah´ı resulta que llegar hasta el nivel Nes O(N). Al ser la reducci´on del problema del problema de la N-alcanzabilidad en Sal de la N-alcanzabilidad en Fpolin´omica en el tama˜no de S, y ser tambi´en grafo de alcanzabilidad de Fde tama˜no polin´omico en N, es claro que el problema de la N-alcanzabilidad se puede resolver en tiempo polin´omico respecto al tama˜no de los datos del problema. Como vemos, esto establece de nuevo una gran diferencia entre la complejidad de los sistemas de FSMs en comunicaci´on generales y los que tienen la limitaci´on de tener los buffers acotados. 10.2. El problema de regreso al estado inicial Analizamos ahora otro problema de decisi´on interesante en el caso de los sistemas de m´aquinas de estados o, en general, de distintos tipos de aut´omatas: el problema de saber si desde cualquier configuraci´on alcanzable se puede regresar a la configuraci´on inicial. De nuevo, este problema resulta en su versi´on general indecidible para nuestros sistemas fruto del Teorema de Rice, pero podemos crear versiones finitistas que sean decidibles e interesantes al mismo tiempo. En este caso la pregunta ser´a: para cualquier secuencia de Mpasos de nuestro sistema, ¿existe un camino de longitud k, con k≤N, de forma que tras esos M+kpasos el sistema vuelva a su configuraci´on inicial? Consideraremos MyNprefijados, como datos del problema. Este problema se puede expresar de forma l´ogica como (a modo de pseudoc´odigo): ∀paso1, paso2, . . . , pasoM∃paso0 1, paso0 2, . . . , paso0 k es igual(inicial, aplicar(inicial, [paso1, . . . , pasoM, paso0 1, . . . , paso0 k])) Como podemos aplicar acciones sobre nuestros sistemas en tiempo polin´omico y la cantidad de pasos es tambi´en polin´omica en MyN, es claro que este problema es del tipo ∀P∃PP, es decir, que pertenece a la clase de complejidad ΠP 2. Lo interesante va a ser comprobar que de hecho este problema es completo dentro de esta clase, lo cual nos da la idea de que es en realidad dif´ıcil de resolver. Para ello, vamos a reducir un problema del tipo del de SAT a nuestro problema. En concreto, ser´a el problema QSAT2(tambi´en llamado QBF2), que trata de determinar si una f´ormula de SAT con ciertos cuantificadores sobre variables (en este caso primero ciertos cuantificadores universales y despu´es otros existenciales, necesariamente en ese orden) es satisfactible. Y es bien sabido que este problema es Πp 2-completo (al igual que sus an´alogos QSATken Πp k), pues de hecho son los problemas m´as protot´ıpicos con esta propiedad. La idea para la simulaci´on de este problema es construir un sistema de FSMs en comunicaci´on que simule exactamente lo que esperamos en el problema QSAT2: habr´a una primera fase en la que asignaremos cualquier valor a ciertas variables de nuestra f´ormula (y para conseguir potencialmente cualquier asignaci´on, usaremos el Cap´ıtulo 10 - Complejidad de algunas propiedades 59 presentar un resultado que no se deduce directamente de las propiedades de otro tipo de m´aquinas, y puede resultar interesante. Con lo discutido en los anteriores p´arrafos, resulta razonable definir el problema de la acotaci´on finita de la siguiente forma: dado un n´umero natural ky una configuraci´on inicial de un sistema de FSMs en comunicaci´on, ¿hay alguna configuraci´on alcanzable en la cual alguno de los buffers tenga al menos kliterales? Proposici´on 10.5. El problema de la acotaci´on finita para sistemas de FSMs en comunicaci´on es PSPACE-completo. Demostraci´on. Es sencillo comprobar que el problema es PSPACE: si el sistema tiene nm´aquinas y kes la constante de acotaci´on del input (que, como anteriormente, suponemos que viene dada en base unaria), como el sistema de FSMs no va a tener nunca m´as de nk literales (en caso de que se cumpla el problema), ser´a sencillo simularlo con nk posiciones en la memoria de una m´aquina de Turing. Adem´as, codificando los buffers de cada FSM en una cinta diferente de la m´aquina de Turing, es f´acil darse cuenta de que podemos simular el sistema con una m´aquina de Turing de tama˜no polin´omico respecto al tama˜no de nuestro sistema de FSMs (donde este tama˜no viene representado por el n´umero de estados que tienen las distintas m´aquinas). Como podemos ver, esta construcci´on usa una cantidad polin´omica de espacio respecto al tama˜no del input y simula perfectamente el sistema de FSMs si sus buffers est´an acotados; as´ı que el problema es en efecto PSP ACE. Y que sea PSPACE-duro lo podemos deducir del resultado que hemos comentado antes sobre la aceptaci´on en LBAs. Por tanto, vamos a hacer una reducci´on de este problema sobre aceptaci´on en LBAs a nuestro problema de sistemas de FSMs en comunicaci´on, que sea adem´as polin´omica. Para cada LBA Fy palabra ω, podemos construir un sistema Sde FSMs en comunicaci´on que lo simule, que tendr´a kliterales al inicio de su ejecuci´on entre todos los buffers. En concreto, lo haremos de forma que los outputs no proliferen. Esto nos asegura que podemos conseguir simular todo el proceso de aceptaci´on (o no aceptaci´on) de ωsin que en Saumente el n´umero de literales entre todos los buffers (propiedad de los sistemas donde los outputs no proliferan). A˜nadimos al final una modificaci´on a Spara resolver el problema: en caso de que Facepte ω,Sllegar´a a una de sus configuraciones de aceptaci´on. Y de cada una de estas configuraciones de aceptaci´on de Ssimplemente tenemos que a˜nadir alg´un estado que entre en bucle a producir literales sin parar. De esta forma Sser´a un sistema donde los outputs pueden proliferar, y donde de hecho, solo habr´a alg´un buffer que tenga al menos k+1 literales en el caso de que se haya llegado a estos estados en los cuales se producen literales descontroladamente, lo cual solo puede ocurrir si Facepta ω. De esta forma deducimos que Sno es k+ 1 acotado si y solo si Facepta ω, y la transformaci´on ha sido polin´omica en el tama˜no de Fyω. Al ser el problema de si Facepta ω PSPACE-completo, tambi´en lo ha de ser el de la acotaci´on finita de sistemas de FSMs. Con esto hemos comprobado que en sistemas de FSMs en comunicaci´on, dada su gran expresividad, hay problemas de gran variedad de complejidades, y tenemos Cap´ıtulo 10 - Complejidad de algunas propiedades 60 tambi´en una idea de cu´al es esta complejidad para algunos de los problemas m´as interesantes de los modelos concurrentes que se aplican a nuestros sistemas. Este es por tanto un buen punto de partida al intentar usar este tipo de sistemas. Cap´ıtulo 11 Un sistema Turing universal En la teor´ıa de computabilidad ha sido siempre un problema interesante conseguir m´aquinas de Turing universales lo m´as peque˜nas o sencillas posible. Se han llegado a construir m´aquinas muy peque˜nas: ya en 1962 M. Minsky encontr´o una con ´unicamente 7 estados y un alfabeto de 4 s´ımbolos, y esto ha ido mejor´andose hasta llegar, por ejemplo, a una m´aquina con solo 2 estados (aunque 18 s´ımbolos en el alfabeto) u otra con 3 estados y 9 literales en su alfabeto (ambas propuestas por Y. Rogozhin en 1996 [24]). Relajando la noci´on de Turing completitud a m´aquinas de Turing que usan una cinta inicial un tanto modificada, que no tenga a ambos lados infinitos s´ımbolos de blanco (como vamos a ver en la teor´ıa que desarrollaremos en las siguientes p´aginas), se han llegado a conseguir m´aquinas de Turing universales con solo 2 estados y 4 s´ımbolos en el alfabeto (por T. Neary y D. Woods en 2007 [22]); resultados que ya son bastante dif´ıciles de superar, e incluso podr´ıa ser que en algunos casos fueran ´optimos. En nuestro caso, vamos a construir un sistema de FSMs en comunicaci´on con 36 estados en total que sea universal, y que tenga un alfabeto con solo 3 literales. No supone ni mucho menos un n´umero tan bajo como los r´ecords que coment´abamos antes, pero supone un resultado interesante en t´erminos de simplicidad: esencialmente el funcionamiento del sistema est´a concentrado en ´unicamente 4 estados, y la mayor´ıa del resto estar´an casi repetidos, pues tendr´an una estructura muy bien definida que vamos a iterar. Consideramos por tanto interesante este resultado porque resulta mucho m´as intuitivo de entender que muchas otras de las m´aquinas que en su momento constituyeron un r´ecord, que son m´as artificiales en cuanto a sus m´etodos de construcci´on y se entiende, por tanto, peor la forma en que funcionan. La construcci´on que haremos est´a basada en el aut´omata 110, un aut´omata celular cuyo comportamiento aparentemente sencillo contrasta con la propiedad b´asica por la cual es conocido: es Turing completo. Recordemos que los aut´omatas celulares son aquellos que tienen una serie de posiciones (normalmente con formas regulares, como en forma de cuadr´ıcula o alineados), pudiendo estar cada posici´on en una cantidad finita de estados en cada instante. Y estos aut´omatas van evolucionando con el tiempo de forma que el estado de cada posici´on en el tiempo t+ 1 depende ´unicamente de del estado de sus posiciones vecinas en el instante t(siendo esta relaci´on de vecindad y la forma de cambiar de cada posici´on diferente en cada aut´omata). En este sentido, el aut´omata 110 simplemente opera en paralelo sobre un vector infinito de celdas (que podemos ver como la cinta de una m´aquina de Turing), de 61 Cap´ıtulo 11 - Un sistema Turing universal 62 forma que en cada movimiento genera una nueva cinta completa, en la cual cada posici´on depende ´unicamente de su valor en la cinta en el instante anterior y la de sus dos posiciones inmediatamente adyacentes. El alfabeto de cinta se supone binario (aqu´ı trabajaremos con 0 y 1). Las transiciones se pueden ver en la siguiente tabla, que muestra cu´al es el valor de una celda en el instante t+ 1 sabiendo el valor que ten´ıan sus 3 celdas vecinas en el instante t(la de su izquierda, ella misma y la de su derecha, en ese orden): Cinta en t111 110 101 100 011 010 001 000 Cinta en t+101101110 Si interpretamos estas transiciones como un n´umero en decimal, resulta ser el 110 (de un total de 256 aut´omatas diferentes que podr´ıan definirse del mismo modo), de ah´ı el nombre del aut´omata. Para simular el comportamiento del aut´omata 110, usaremos un enfoque similar al del apartado 6.2, en el cual nuestro sistema barr´ıa de izquierda a derecha la cinta de la m´aquina de Turing, generando as´ı una nueva cinta tras cada barrido. En este caso se aplica tambi´en la idea de retrasar los outputs un ciclo respecto a los inputs: antes era porque el cabezal pod´ıa moverse a la izquierda, y ahora es debido a que cada letra puede afectar a la que est´a a su izquierda cuando el aut´omata genere un output para la siguiente posici´on de la cinta. Visto de otro modo, a la hora de ir recorriendo de izquierda a derecha la cinta, hemos de recordar los dos valores que acabamos de ver, y solo a la hora de ver el tercero tomaremos la decisi´on de sacar un output, que estar´a un ciclo retrasado conforme a la idea que propone el aut´omata 110 (podr´ıamos decir que el nuevo valor de una celda se genera cuando visitamos el valor antiguo de su vecina derecha), si bien no supone un problema. A modo de ejemplo tenemos la figura 11.1: si at irepresenta el contenido de la posici´on ide la cinta en el instante t, entonces las flechas diagonales lisas indican cu´ando se genera cada literal de la cinta de t= 1, mientras que las flechas discontinuas nos indican qu´e otras posiciones hemos tenido que tener en cuenta para generar dicha posici´on, y que por lo tanto, de alguna manera nuestro sistema ha de recordar. a0 0a0 1a0 2a0 3a0 4 a1 0a1 1a1 2a1 3a1 4 Figura 11.1: Representaci´on gr´afica de c´omo se retrasan las producciones. Resulta necesario pensar tambi´en en una forma de delimitar la cinta actual, pues no queremos que el final de la cinta en el instante tinfluya en los outputs generados Cap´ıtulo 11 - Un sistema Turing universal 63 al inicio de la cinta del instante t+ 1. Para ello introduciremos el literal #, como ya hicimos anteriormente, que denotar´a el fin de una cinta y, a la vez, el comienzo de la siguiente. Con estas ideas, podr´ıamos crear un aut´omata bastante sencillo que simule el funcionamiento del aut´omata 110, como representamos en la siguiente figura: # 0 1 00 01 10 11 0/ 1/ 0/ 1/ 0/ 1/ 0/0 1/1 0/1 1/10/0 1/1 0/1 1/0 #/# #/# #/# #/# #/# #/# #/# Figura 11.2: Implementaci´on de la FSM que simula las producciones del aut´omata 110. Como vemos, esencialmente estos 7 estados ya aglutinan el funcionamiento del aut´omata 110, y por tanto simulan algo que tiene tanta expresividad como para ser Turing completo. Adem´as, los 4 estados 00, 01, 10, 11 son los que llevan la mayor parte del significado, pues los otros 3 solo reflejan una especie de estado transitorio del sistema, en el cual todav´ıa no hemos le´ıdo suficientes caracteres como para generar un output. Pero ahora se nos presenta la mayor dificultad de la construcci´on: la demostraci´on de que el aut´omata 110 es Turing completo, llevada a cabo por Matthew Cook en 2004 [8,9] para dar una contestaci´on positiva a la conjetura de Stephen Wolfram en 1985, presupone que la cinta es un poco diferente a lo que estamos acostumbrados: no est´a rellena entera de caracteres blancos a izquierda y derecha de la zona que estamos tratando, sino que supone que hay un patr´on repetitivo que se repite indefinidamente hacia izquierda y derecha. Cook llama a este patr´on repetitivo ´eter, y es la cadena 00010011011111, de longitud 14. Al aplicar la regla del aut´omata 110 sobre el ´eter, este se desplaza 4 posiciones a la izquierda. De este modo, tras 7 iteraciones, obtenemos de nuevo el ´eter en su posici´on inicial, y todo se repite c´ıclicamente. Cap´ıtulo 11 - Un sistema Turing universal 64 000100110111110001 001101111100011000 ··· ··· ··· ··· Figura 11.3: Una iteraci´on de la evoluci´on del ´eter. Lo que nos falta entonces para conseguir que nuestro sistema simule realmente el aut´omata 110 de forma que consigamos un sistema Turing universal es, de alguna forma, simular el ´eter. Para ello introduciremos dos m´aquinas adicionales: una simular´a la creaci´on de ´eter a la derecha de la zona de la cinta que estamos tratando (F2), y otra a la izquierda (F0). La m´aquina que simulaba el aut´omata 110 y que hemos explicado en la figura anterior ser´a la m´aquina F1. Tendremos por tanto un sistema Scon 3 m´aquinas que se comunicar´an de manera c´ıclica: F0le mandar´a la cinta completa a F1,F1aF2la nueva cinta generada, F2aF0la cinta habiendo a˜nadido un car´acter por la derecha, y cuando le llegue de nuevo a F1a trav´es de F0, esta habr´a a˜nadido un car´acter m´as del ´eter por la izquierda. Como comentamos, tras cada barrido de la cinta, tanto F0como F2a˜nadir´an un car´acter nuevo a la cadena que est´a procesando el sistema S. Esto hace que cada vez haya m´as literales en Sy que no todos sean especialmente relevantes (pues la mayor´ıa van a continuar siguiendo el patr´on del ´eter, porque las modificaciones no se han extendido tanto). Sin embargo, es una manera f´acil de resolver la cuesti´on de la simulaci´on del ´eter, porque si no, tendr´ıamos que crear un m´etodo de detecci´on de qu´e zonas de la cinta han cambiado o no en cada momento, lo cual resultar´ıa mucho m´as costoso. Sin m´as dilaci´on, pasamos a definir F0. Como forzosamente el sistema tiene que recordar en cu´al de los 14 elementos del periodo del ´eter est´a (por la izquierda en este caso), F0tiene que tener al menos 14 estados. Veamos que basta con 14: definimos un estado qi(para cada i∈ {0,...,13}) de forma que si F0est´a en el estado qi, esto significa que el siguiente literal a la izquierda de la regi´on de la cinta que la m´aquina F1ha considerado hasta ahora es el i-´esimo del patr´on del ´eter, que recordemos que es 00010011011111. Como sabemos que, tras una pasada de las m´aquinas, el ´eter se desplaza 4 posiciones a la izquierda. Eso nos quiere decir que, si en el tiempo ten una posici´on de la cinta est´abamos en el car´acter idel ´eter, en el instante t+1 en esa posici´on estar´a el car´acter i+ 4 (m´odulo 14, claro). Pero como ese car´acter lo habr´a introducido F0en el sistema en tiempo t, y ahora estamos interesados en el car´acter justo a su izquierda, es decir, en el i+ 3 del ´eter. Por tanto, de qitransitaremos a q(i+3) m´od 14. Con esto se nos crea una estructura muy regular y sencilla que nos permite generar ´eter paso a paso a la izquierda de la zona que est´a tratando nuestro sistema hasta el momento. Una vez tenemos esto claro, solo tenemos que darnos cuenta de cu´al es el funcionamiento que esperamos de F0: deber´ıa reenviar todo lo que lee, y ´unicamente a˜nadir una letra en la siguiente cinta, es decir, que solo a˜nade la letra correspondiente del ´eter cuando le llega el car´acter # (lo cual hacemos, por simplicidad, generando 2 outputs al consumir el input #, lo cual vimos ya tras la definici´on 5.1 que era una Cap´ıtulo 11 - Un sistema Turing universal 65 forma razonable de interpretar el fen´omeno subyacente de proliferaci´on de los outputs). Todo este pensamiento quedar´ıa plasmado en un aut´omata de la forma que mostramos en la figura 11.4. q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11 q12 q13 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 #/#0 #/#0 #/#0 #/#1 #/#0 #/#0 #/#1 #/#1 #/#0 #/#1 #/#1 #/#1 #/#1 #/#1 Figura 11.4: Implementaci´on de F0en la construcci´on. Una vez entendida la construcci´on del aut´omata F0, la construcci´on de F2resulta sencilla por analog´ıa. Las transiciones cambiar´an poco, pues desde el estado qi transitaremos al q(i+5) m´od 14 porque estamos interesados en la posici´on a la derecha de la i+ 4, no en la izquierda como en F0. Y de nuevo, F2solo a˜nade literales al sistema una vez sabe que le ha llegado el fin de la cinta, es decir, cuando lee #. Esto nos dar´ıa el aut´omata de la figura 11.5. Cap´ıtulo 11 - Un sistema Turing universal 66 q0q1q2q3q4 q5q6q7q8q9 q10 q11 q12 q13 q0 8 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 0/0 1/1 #/0# #/0# #/0# #/1# #/0# #/0# #/1# #/1# #/0 −/# #/1# #/1# #/1# #/1# #/1# Figura 11.5: Implementaci´on de F2en la construcci´on. Por ´ultimo, comentamos c´omo se inicia todo el procedimiento de simulaci´on: en F1el estado inicial es #; en F0es q0; y en F2es q0 8(que hemos separado de q8para que al inicio solo se produzca la # que necesitamos). Adem´as, el input se pondr´a en el buffer del que lee F2. As´ı, habr´a una primera vuelta en la cual F2 a˜nade # y F0yF2la reenv´ıan. Por tanto, el buffer de F2ahora tendr´a el input inicial seguido de #. Y con eso ya empieza el reconocimiento usual, y F2empieza a a˜nadir caracteres correctamente porque est´a en q13 (y el ´eter va hacia la izquierda), yF0estaba a˜nadiendo partes correctas del ´eter desde el principio. Cap´ıtulo 12 Conclusiones A la vista de todo el trabajo expuesto hasta ahora, ya podemos extraer varias conclusiones interesantes sobre los sistemas de m´aquinas de estados finitos en comunciaci´on. Lo primero que hemos comprobado es que dentro del mismo marco te´orico tienen cabida diferentes definiciones, y cada una de ellas implica diferentes propiedades de los sistemas. En concreto, las versiones m´as usuales tienen una expresividad bastante alta y est´an siempre en la l´ınea entre lo decidible y lo indecidible (como hemos visto en los cap´ıtulos 4,6,8y9). El hecho de que est´en en esta frontera motiva la variedad de definiciones que tenemos: dependiendo del caso estaremos interesados en una ganancia en expresividad o en comprensi´on de nuestros sistemas, y elegiremos versiones en uno u otro lado de la frontera dependiendo de estos intereses. En concreto, sabemos que los sistemas de m´aquinas de estados generales son Turing completos (cap´ıtulo 4) y eso hace que los problemas de decisi´on asociados a ellos sean indecidibles (Teorema de Rice). Pero adem´as, versiones simplificadas de estos problemas de decisi´on (que hemos estudiado en el cap´ıtulo 10) son tambi´en dif´ıciles de resolver en general, como el caso de la alcanzabilidad finita, que hemos comprobado que es NP-completo. Adem´as, por ser Turing completo, podemos construir sistemas que sean universales. En este caso ha sido interesante la construcci´on basada en el aut´omata 110 (cap´ıtulo 11) por ser simple y sencilla de entender, adem´as de relativamente peque˜na. Respecto a las diferentes modificaciones podemos decir tambi´en varias cosas. Sabemos que los sistemas donde los outputs no proliferan son completos dentro de los reconocedores de lenguajes dependientes del contexto, lo que los sit´ua cerca de la Turing completitud, pero hace que sean m´as sencillos de estudiar a pesar de esa gran expresividad. En concreto hemos podido comprobar que algunos problemas de vital importancia, como el de saber si aceptan un input dado, es decidible, aunque tiene una complejidad muy elevada (vimos que era PSPACE-completo en el cap´ıtulo 10). El caso de los sistemas donde los buffers est´an acotados es m´as sencillo. Comprobamos que son equivalentes a los aut´omatas finitos en el cap´ıtulo 7y que eso hace que problemas anteriormente estudiados como la alcanzabilidad finita sean polin´omicos (en el cap´ıtulo 10). Era m´as interesante el caso de los sistemas donde los buffers no tienen orden, estudiados en el cap´ıtulo 8. En este caso, diferentes adaptaciones de la definici´on llevaban a la equivalencia con diferentes redes de Petri: las usuales, con arcos inhibidores o con arcos restablecedores. En todos los casos resultaba interesante la 67 Cap´ıtulo 12 - Conclusiones 68 comparativa entre la complejidad de ciertos problemas b´asicos como la alcanzabilidad o el recubrimiento, que est´an en la frontera de lo decidible e indecidible en estos tres tipos de redes de Petri, como vimos al final del cap´ıtulo. Por ´ultimo estudiamos una variaci´on en la cual los canales de comunicaci´on pueden fallar, dando lugar al formalismo (ampliamente estudiado en la literatura) de los Sistemas de Mensajes Perdidos. Hemos recopilado algunos de las propiedades b´asicas de estos sistemas en el cap´ıtulo 9, como que el problema de la terminaci´on es decidible (aunque de una complejidad extremadamente alta). Con esto hemos establecido una teor´ıa b´asica bastante amplia sobre sistemas formados por m´aquinas de estados finitos en comunicaci´on, que puede servir en muchos otros trabajos como referencia de qu´e propiedades son esperables dependiendo de las caracter´ısticas que tengan nuestros canales de comunicaci´on. Adem´as hemos expuesto una colecci´on bastante amplia de variaciones en la definici´on principal, de forma que todos estos modelos se podr´an reutilizar en casos en los que tengamos que implementar protocolos en los cuales m´aquinas sencillas tienen que comunicarse para realizar una tarea m´as compleja.