An´alisis de sis emas
de M´aquinas de Es ados Fini os en comunicaci´on
Analysis o Communica ing Fini e S a e Machines
Pablo Hidalgo Palencia
DOBLE GRADO EN INGENIER´
IA INFORM´
ATICA Y MATEM´
ATICAS
FACULTAD DE INFORM´
ATICA
UNIVERSIDAD COMPLUTENSE DE MADRID
T abajo de Fin de G ado de Ingenie ´ıa In o m´a ica
Cu so 2019/2020
Di ec o es:
Ismael Rod ´ıguez Laguna
Fe nando Rosa Vela do
i
Resumen
En es e abajo p esen amos un modelo de c´ompu o o mado po a ias m´aqui-
nas de es ados ini os que se pueden comunica en e s´ı a a ´es de canales FIFO.
Es udiamos cu´al es su exp esi idad y la complejidad de esol e algunos p oblemas
en es e modelo, que yace en e lo decidible y lo indecidible po auna la simplicidad
de las m´aquinas de es ados ini os con la complejidad que apo an comunicaciones
no de e minis as. Es udiamos adem´as di e sas a iaciones en la de inici´on y las im-
plicaciones que ienen es as modi icaciones sob e la exp esi idad y complejidad del
modelo.
Palab as cla e
M´aquinas de es ados ini os, m´aquinas de es ados ini os en comunicaci´on, sis e-
mas de mensajes pe didos, edes de Pe i, au ´oma a 110.
ii
Abs ac
In his wo k we p esen a compu a ion model in which se e al Fini e S a e Machi-
nes communica e ia FIFO channels. We s udy i s exp essi i y and he complexi y
o sol ing some decision p oblems ega ding his model, lying on he edge be ween
decidabili y and undecidabili y because o b inging oge he he simplici y o Fini e
S a e Machines and he complexi y o non-de e minis ic communica ions. We also
s udy some a ia ions o he main model and he changes hey gene a e in e ms o
exp essi i y and complexi y.
Keywo ds
Fini e S a e Machines, Communica ing Fini e S a e Machines, Lossy Channel
Sys ems, Pe i ne s, ule 110.
´
Indice gene al
1. In oducci´on 1
2. Es ado del a e 5
3. De inici´on de los sis emas con 2 m´aquinas 7
3.1. Sis emas donde los ou pu s no p oli e an ................ 10
4. Exp esi idad de los sis emas 12
5. De inici´on gene al de los sis emas 15
5.1. Sis emas con bu e s aco ados ...................... 17
6. Sis emas donde los ou pu s no p oli e an 19
6.1. Ejemplo de uncionamien o ....................... 19
6.2. Exp esi idad de los sis emas donde los ou pu s no p oli e an . . . . 21
7. Sis emas con bu e s aco ados 32
8. Sis emas con bu e s sin o den 35
8.1. Exp esi idad de los sis emas con bu e s sin o den .......... 36
8.2. Compa a i a con o os ipos de edes de Pe i ............. 39
9. Sis emas de Mensajes Pe didos 43
9.1. In oduciendo jus icia en las ejecuciones ................ 44
10.Complejidad de algunas p opiedades 47
10.1. El p oblema de la alcanzabilidad ini a ................. 47
10.1.1. En sis emas con bu e s aco ados ................ 51
10.2. El p oblema de eg eso al es ado inicial ................ 52
10.3. O os p oblemas de complejidad mayo ................. 58
iii
´
INDICE GENERAL i
11.Un sis ema Tu ing uni e sal 61
12.Conclusiones 67

Cap´ı ulo 1
In oducci´on
En la li e a u a cien ´ı ica, en pa icula en la de la In o m´a ica, es ecuen e
encon a se si uaciones en las cuales los in es igado es ienen un p oblema que e-
sol e que no se ajus a pe ec amen e a ning´un modelo p ees ablecido conocido, si
bien puede se sol en ado de o ma sencilla c eando un modelo ad hoc pa a la si-
uaci´on a pa i de o os ya es udiados en p o undidad. Po ejemplo, en nume osas
ocasiones, al en en a se a cie os p oblemas, los au o es deciden di idi el p oblema
en a ias secciones sencillas e in e conec a las en e s´ı. No emos que es o ambi´en
se hace en la ida eal: la mayo ´ıa de los abajos complejos se suelen ealiza di-
idi´endolos en pa es m´as peque˜nas y sencillas (que pod ´an se ´an ealizadas po
di e en es pe sonas) y despu´es jun ´andolas.
Es e es el caso de nues o es udio: es ecuen e que al ene que modeliza p o-
ocolos concu en es en la In o m´a ica, po ejemplo, se u ilice la misma ´ac ica que
comen ´abamos. En conc e o, el p o ocolo se ealiza po medio de ins ancias pe-
que˜nas m´as sencillas, como pueden se las que ealizan las m´aquinas de es ados
ini os, elemen os bas an e sencillos y es udiados; es ableciendo una comunicaci´on
en e las dis in as m´aquinas pa a que puedan simula el p o ocolo comple o.
No obs an e, es as cons ucciones complejas hechas a pa i de m´aquinas de
es ados sencillas se suelen hace ad hoc pa a la si uaci´on en la que se es ´e in e esado,
y es o hace que en gene al no se puedan eu iliza cie os esul ados ya exis en es
en ejemplos simila es en la li e a u a.
En es e abajo p e endemos hace un es udio m´as gene al sob e es os sis emas
o mados po m´aquinas de es ados en comunicaci´on, de o ma que pueda es able-
ce unas bases pa a sabe qu´e p opiedades pod ´ıa ene un sis ema conc e o que
u ilicemos en o os abajos con un in m´as de e minado. Po ejemplo, si pa a una
in es igaci´on pos e io usamos un modelo simila a los que amos a explica en es e
es udio, ¿ esul a ´an p opiedades de decisi´on b´asicas como e minaci´on o alcanzabi-
lidad decidibles o a ables? Los esul ados que e emos en los siguien es cap´ı ulos
ayuda ´an a esponde es e ipo de p egun as.
Adem´as, dada la a iabilidad y e sa ilidad de es e ipo de sis emas, esul a ´a
in e esan e in es iga sus p opiedades en unci´on de los di e en es ipos de de inici´on
que podamos hace de ellos, po lo cual a a emos a ios ipos de sis emas pa a
pode es ablece compa a i as en e sus p opiedades, lo que c eemos que pod ´ıa se
de u ilidad a la ho a de e nos en la necesidad de usa alguno de es os sis emas.
El ex o i ´a o ganizado po cap´ı ulos. En el cap´ı ulo 2da emos una isi´on am-
plia sob e li e a u a elacionada con nues o abajo. En el cap´ı ulo 3 e emos una
1
Cap´ı ulo 1 - In oducci´on 2
de inici´on de un modelo simpli icado de los sis emas de m´aquinas de es ados en co-
municaci´on, que nos ayuda ´a a comp ende mejo los concep os an es de en a en
el caso gene al. En el cap´ı ulo 4 e emos que es a simpli icaci´on de los sis emas es
un modelo Tu ing comple o. Con es o, en el cap´ı ulo 5llegamos ya a la de inici´on de
los sis emas gene ales que a a emos a pa i de ah´ı. En el cap´ı ulo 6es udia emos
m´as a ondo el caso de los sis emas donde los ou pu s no p oli e an, que esul an se ,
como econocedo es de lenguajes, un modelo comple o den o del de los dependien-
es del con ex o. En el siguien e cap´ı ulo, el 7, explicamos que los sis emas donde
los bu e s es ´an aco ados no pueden econoce m´as all´a de los lenguajes egula es.
En el cap´ı ulo 8es udiamos qu´e ocu e en el caso de que se pie da el o den de los
mensajes in e cambiados en nues os sis emas, ya que ob enemos modelos compa a-
bles a di e en es ipos de edes de Pe i, los modelos m´as ep esen a i os cuando no
hay o den en los sis emas. M´as a de, en el cap´ı ulo 9, es udiamos qu´e ocu e cuan-
do o a p opiedad b´asica de los sis emas cambia, conc e amen e qu´e ocu e cuando
los canales de comunicaci´on pueden alla , y su elaci´on con los conocidos Sis emas
de Mensajes Pe didos. T as odo es o, llegamos al cap´ı ulo 10, donde es udiamos
la complejidad de esol e di e en es p oblemas de decisi´on sob e las cualidades de
nues os sis emas, cen ´andonos en el p oblema de la alcanzabilidad ini a y de e-
g eso al es ado inicial. Po ´ul imo, p esen amos en el cap´ı ulo 11 un sis ema bas an e
sencillo que es Tu ing uni e sal, po medio de una simulaci´on del au ´oma a 110.
In oduc ion
As we can see in he exis ing scien i ic li e a u e, i is qui e usual ha a esea che
aces a p oblem which does no i exac ly in an exis ing model, bu can be easily
sol ed c ea ing an ad hoc model o his si ua ion based on o he s which ha e been
s udied in dep h. Fo ins ance we can ind he si ua ion whe e a esea che spli s
a p oblem in o smalle and simple sec ions and hen connec s all hem p ope ly.
No ice ha his is no a unique ea u e om esea ch, we do his in ou daily li e: we
ca y ou he as majo i y o he di icul wo ks using a s a egy ha i s di ides
he whole ask in o smalle sub asks (which a e commonly done by di e en people)
and hen join e e y hing.
This will be ou case: o ins ance i is common ha he s a egy explained abo e
is used when modelling concu en p o ocols in Compu e Science. Mo e conc e ely,
he p o ocol is ca ied ou by means o smalle sys ems, such as Fini e S a e Ma-
chines -which a e eally simple and ha e been s udied b oadly- which can join hei
e o s i we es ablish some kind o communica ion among hem.
Al hough his is a common si ua ion, hese complex cons uc ions a e o en in
p ac ice eally ad hoc, in he sense ha hey a e no di ec ly eusable in o he
si ua ions han he one hey we e hough o . This makes i mo e di icul o euse
no only he de ini ions, bu also he esul s and p ope ies ha we e p o ed o
hose models.
In his wo k we aim o s udy in a b oad gene ali y his kind o sys ems whe e
some Fini e S a e Machines can communica e among hem, wi h he pu pose o
es ablishing some ounda ion in he opic which can be la e used o know which
kind o p ope ies a e o expec om a conc e e simila model ha anyone could
need in a esea ch. I i we e he case ha we used a simila model in ano he wo k,
would some basic p ope ies o ha model such as e mina ion o eachabili y be
decidable o ac able? The esul s we a e abou o de elop in he nex chap e s will
help o answe his so o ques ions.
Fu he mo e, gi en he a iabili y and lexibili y o his kind o sys ems, i will
be o g ea in e es o in es iga e hei p ope ies in e ms o he di e en de ini ions
we can use, in o de o s a e a compa a i e among some o he possible models ha
can be c ea ed om he same abs ac ion. This can u n ou o be eally use ul
when deciding which model bes i s a conc e e si ua ion we a e in e es ed in.
The ex will be di ided in o chap e s. In Chap e 2we will ake a look a he
exis ing li e a u e ela ed o ou wo k. In Chap e 3we will in oduce he opic by
s udying a simpli ied e sion o ou inal model, which only comp ises a maximum
o wo Fini e S a e Machines, and will help us unde s and be e he key concep s.
In Chap e 4we p o e ha his simpli ied model is Tu ing comple e. In Chap e 5
we a i e o he de ini ion o he main model we a e in e es ed in. In Chap e 6we
3
Cap´ı ulo 1 - In oducci´on 4
s udy a submodel whe e he amoun o in o ma ion used o communica e is limi ed
( he Fini e S a e Machines can communica e wi h only one machine a a ime),
which esul s o be comple e among he con ex -sensi i e language ecognize s. We
s udy nex , in Chap e 7, he case whe e he size o he bu e s used o communica e
is bounded, which esul s in a model ha can only ecognize egula languages. In
ou pa h s udying a ia ions o he main model we ge o he Chap e 8, whe e he
o de o he messages exchanged be ween machines is in some sense los , and he
esul ing model is compa able o di e en kinds o Pe i ne s. In Chap e 9we s udy
he case whe e ano he c ucial p ope y o he communica ions is changed: i he
channels used o communica ions a e aul y, he o malism becomes eally simila
o Lossy Channel Sys ems, and we will s udy he connec ions mo e in de ail. All his
been s udied we a i e o Chap e 10, whe e we look in o some decision p oblems on
ou models and hei complexi y, ocusing on some ini a y e sions o eachabili y
and home-s a e p oblems. Finally in Chap e 11 we p esen a eally simple sys em
which is (Tu ing-)uni e sal, based on Rule 110.
Cap´ı ulo 3 - De inici´on de los sis emas con 2 m´aquinas 11
como mucho an os ou pu s como inpu s consumen, deducimos que la can idad
de li e ales en S, es deci , |B1|+|B2|nunca puede c ece a lo la go de cualquie
ejecuci´on.

Cap´ı ulo 4
Exp esi idad de los sis emas
Una ez cla as las de iniciones, amos a es udia p ime amen e cu´al es la exp e-
si idad de los sis emas que acabamos de de ini . Va a esul a in e esan e comp oba
que, a pesa de la simplicidad de las de iniciones, los sis emas de FSMs en comuni-
caci´on son Tu ing comple os. Pa a la demos aci´on de es e hecho nos basa emos en
una compa a i a con los au ´oma as con cola, que p esen amos aqu´ı b e emen e.
De inici´on 4.1. Un au ´oma a con cola Mes una upla M= (Q, Σ,Γ,$, q0, δ),
donde Qes un conjun o ( ini o) de es ados, Σ⊂Γes el al abe o usado po los inpu s,
Γes el al abe o que usa la cola, $∈Γ Σes el s´ımbolo inicial de la cola, q0∈Qes
el es ado inicial de Myδ:Q×Γ→Q×Γ∗es la unci´on de ansici´on.
La unci´on de ansici´on ac ´ua de o ma simila al caso de los au ´oma as con pila,
que ambi´en u ilizan cie a memo ia adicional, pe o en es a ocasi´on u ilizando una
es a egia LIFO: las ansiciones oman un li e al del p incipio de la cola y de uel en
a ios li e ales que se me en po el inal de la cola. Cabe menciona ambi´en que los
au ´oma as con cola acep an po cola ac´ıa.
Lo m´as in e esan e pa a noso os en es e momen o es que los au ´oma as con co-
la o man un sis ema Tu ing comple o, pues pueden simula cualquie m´aquina de
Tu ing, y de hecho en iempo polin´omico (como se puede consul a en [19], eje cicio
99, po ejemplo). De es o esul a que una demos aci´on sencilla de la Tu ing com-
ple i ud de los sis emas de FSMs en comunicaci´on se base en educi un au ´oma a
con cola a uno de es os sis emas. Adem´as, aunque no hace al a pa a p oba la
Tu ing comple i ud, es a educci´on se puede hace polin´omica, lo cual se ´a de u ili-
dad pos e io pa a demos a o as p opiedades. En el siguien e esul ado amos a
desa olla es a idea en p o undidad.
Teo ema 4.2. El conjun o de sis emas de FSMs en comunicaci´on en los cuales los
ou pu s p oli e an (seg´un la de inici´on 3.1) es Tu ing comple o.
Demos aci´on. Sea M= (Q, Σ,Γ,$, q0, δ) un au ´oma a con cola, seg´un la de-
inici´on an e io 4.1. En onces podemos c ea un sis ema S= (F1, F2), con bu e s
B1, B2, de dos m´aquinas en comunicaci´on que simulen el compo amien o de Mde
o ma que F1simule las ansiciones de M(a a ´es de la unci´on de ansici´on
δ1), mien as que F2simplemen e haga que odos los inpu s que le llegan desde B2
acaben en B1(a a ´es de δ2). De es a o ma, al se los bu e s colas, se compo a ´an
como la cola de nues o au ´oma a M.
No obs an e, hemos de pone a enci´on a la ho a de de ini F1, pues la o ma que
iene Mde hace que los ou pu s p oli e en es gene ando a ios li e ales con una
12
Cap´ı ulo 4 - Exp esi idad de los sis emas 13
misma ansici´on ( eco demos δ:Q×Γ→Q×Γ∗), mien as que F1lo hace un an o
di e en e, a a ´es de su unci´on de ansici´on δ1:Qi×Σ?−→ Q1×Σ?. En el p ime
cap´ı ulo ya imos la in uici´on de que ealmen e es as dos o mas de hace p oli e a
los ou pu s e an equi alen es, y aqu´ı amos a e la cons ucci´on que necesi amos
m´as en de alle.
Pa a cada es ado qi∈Q,F1 end ´a asimismo un es ado q1
i∈Q1. Veamos aho a
qu´e cons ucci´on hacemos pa a simula una ansici´on a bi a ia δ(qi, X) = (qj, α)
de M. Si el ama˜no de αes n∈N, podemos deci que α=Y1+Y2+. . .+Yn, donde
Yk∈Σ son li e ales de nues o al abe o. En el caso de que n < 2 podemos simula
´acilmen e la ansici´on de δincluyendo δ1(q1
i, X)=(q1
j, α). Y en el caso de que n≥
2, simplemen e enemos que a˜nadi n−1 es ados auxilia es q1
i,X,1, q1
i,X,2,··· , q1
i,X,n−1,
jun o con las ansiciones δ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 cons ucci´on la podemos e g ´a icamen e
como en la siguien e igu a:
qiqj
X/α
se con ie e en:
q1
iq1
i,X,1q1
i,X,2q1
i,X,n−1q1
j
X/Y1/Y2··· /Yn
Figu a 4.1: Visualizaci´on de la ans o maci´on pa a que las FSMs solo p oduzcan
un ou pu con cada ansici´on.
Tenemos que ene en cuen a aho a que hay que simula la acep aci´on de M, que
como dijimos es po cola ac´ıa. Al igual que se hace usualmen e con los au ´oma as
con pila, en los cuales se in oduce un s´ımbolo especial que deno a el in de la
pila, aqu´ı in oduci emos el s´ımbolo # con el mismo in. Lo p ime o que ha ´a F1
se ´a gene a dicho li e al desde su es ado inicial q1
#, que end ´a una ´unica ansici´on:
δ1(q1
#, ) = (q1
0,#), donde q1
0es el es ado asociado al es ado inicial q0de M. A pa i
de ah´ı, F1no end ´a en cuen a el li e al #, pues no in luye en la simulaci´on de M.
Po ello, cada es ado q∈Q1ob ia ´a las # median e la ansici´on δ1(q, #) = (q, #).
Vis o es o, la m´aquina F2se ´ıa ealmen e simple, como explic´abamos en la dis-
cusi´on an e io : pod ´ıa simplemen e con a con un es ado q2
0(que se ´ıa el es ado
inicial de F2), y con las ansiciones δ2(q2
0, A)=(q2
0, A) pa a odos los A∈Γ, de
o ma que lo ´unico que hace es de ol e lo que lee. Y iene que ene ambi´en un
mecanismo de de ec a la acep aci´on. Como enemos que simula la acep aci´on de
M, que es po cola ac´ıa, Sdebe ´ıa acep a cuando sus bu e s es ´an ac´ıos. Pe o
pa a ello hemos in oducido el s´ımbolo #: cuando Sllegue a simula a Mcon la
cola ac´ıa, el ´unico s´ımbolo que hab ´a en los bu e s B1, B2se ´ıa #. Po an o, F2
Cap´ı ulo 4 - Exp esi idad de los sis emas 14
puede acep a en cuan o ea # dos eces seguidas. Una ep esen aci´on g ´a ica se
puede e en la igu a 4.2.
q2
0q2
#q2
#/#
A/A (A6= #)
#/
A/A (A6= #)
Figu a 4.2: La FSM F2de nues o sis ema.
De es a o ma, el sis ema que con o man F1,F2simula el au ´oma a M, usando el
al abe o Γ∪{#}, con es ados iniciales (q1
#, q2
0)∈Q1×Q2y es ado inal q2
∈Q2.
No emos adem´as que po cada ou pu que gene a M, pa a simula dicha p oduc-
ci´on de un ou pu nues o sis ema Sp oduce ´unicamen e 2 ou pu s (uno F1y o o
F2) Es o quie e deci que los iempos de ejecuci´on de MySse elacionan ambi´en
con ´unicamen e ese ac o cons an e 2. Po an o, la simulaci´on se hace en iempo
polin´omico espec o a lo que a da M(po cada paso de M,Sda una can idad
O(1) de pasos). En cuan o a espacio ambi´en enemos una ans o maci´on polin´omi-
ca, lo cual podemos e en la can idad de es ados de F1yF2. Y como la educci´on
de m´aquinas de Tu ing a au ´oma as con cola se puede hace ambi´en con ´unica-
men e un aumen o polin´omico de iempo y espacio, concluimos que la educci´on de
m´aquinas de Tu ing a sis emas de FSMs en comunicaci´on es polin´omica.
Cap´ı ulo 5
De inici´on gene al de los
sis emas
Vis o ya el in e ´es que ienen los sis emas de FSMs en comunicaci´on a a ´es de
su g an exp esi idad a pesa de su apa en e sencillez, como acabamos de comp oba
al e que con o man un sis ema Tu ing comple o, pasamos a es udia una gene ali-
zaci´on na u al de los sis emas que hab´ıamos conside ado has a aho a, in oduciendo
un mayo n´ume o de FSMs.
Sean Fi= (Qi, Ii, Oi, q0
i, δi), con 1 ≤i≤n, un conjun o de nFSMs. De-
inimos S= (F1, F2, . . . , Fn) como el sis ema de FSMs en comunicaci´on asocia-
do a F1, . . . , Fn. Es as m´aquinas se comunican en e s´ı a a ´es de cie os bu e s
B1, B2, . . . , Bn, de o ma que Ficonsume li e ales de Bi(desde uno de los ex emos
del bu e ), mien as que cualquie m´aquina puede esc ibi li e ales en Bi(po el
ex emo con a io al que Filee). La con igu aci´on de Sdepende ´a en cada ins an e
del es ado en que es ´a cada m´aquina Fiy del con enido de cada bu e Bi.
Cabe des aca que en es e caso amos a in e p e a los ou pu s de cada m´aquina
Fide una mane a que nos a a esul a m´as c´omoda. Podemos supone que cada
unci´on de ansici´on ha cambiado su ango: δi:Qi×I?
i−→ Qi×O?
in(donde
Qi×O?
in⊆Qi×I?
1×I?
2×···×I?
npa a que la comunicaci´on enga sen ido), ya
que aho a cada ansici´on de Fi a a gene a (po encialmen e) un ou pu pa a cada
una de las m´aquinas de S. No amos adem´as que, al igual que en el caso m´as sencillo
en el cual solo en´ıamos 2 m´aquinas, los co espondien es al abe os de las m´aquinas
ienen que se cohe en es en e s´ı pa a que se pueda es ablece una comunicaci´on
en e ellas. En una si uaci´on gene al, debe ´ıamos ene Oi⊆Ijpa a cada pa
1≤i, j ≤n, de o ma que Fjen iende los li e ales que le manda Fi. En los casos
donde no sea necesa io (y de hecho, esul e engo oso) lidia con es a sue e de
de alles, deno a emos Σ := I1∪I2∪···∪In∪O1∪O2∪···∪Oncomo el al abe o
de odas las m´aquinas de Spo simplicidad, ya que gene aliza al es o de al abe os.
La unci´on de ansici´on global en e las dis in as ansiciones de S oma aho a
la o ma δ:Q1×Σ∗×Q2×Σ∗×···×Qn×Σ∗−→ Q1×Σ∗×Q2×Σ∗×···×Qn×Σ∗
en e las di e en es con igu aciones de Sque nos ayuda a sabe c´omo e oluciona es e
sis ema. Esencialmen e, simula ejecuciones de cada m´aquina po sepa ado, igual que
en el caso de ´unicamen e dos m´aquinas, de o ma que en cada ansici´on de Shay
una m´aquina Fique da un paso en su ejecuci´on: lee de su bu e Bi, a anza en la
di ecci´on que le indique ese li e al le´ıdo y en ´ıa al es o de m´aquinas los li e ales
que la ansici´on le indique, dej´andolos en sus espec i os bu e s. Vis a la in uici´on,
esc ib´amoslo de mane a m´as p ecisa.
15
Cap´ı ulo 5 - De inici´on gene al de los sis emas 16
De inici´on 5.1. Sea un conjun o de nFSMs, F1, F2, . . . , Fn, donde cada m´aquina es
Fi= (Qi, Ii, Oi, q0
i, δi), con unci´on de ansici´on δi:Qi×Σ?−→ Qi×Σ?n, como
an es hemos desc i o. De inimos en onces el sis ema de FSMs en comunicaci´on
asociado a es as m´aquinas como S= (F1, F2, . . . , Fn). Una con igu aci´on de Ses
una upla de Q1×Σ∗×Q2×Σ∗×···×Qn×Σ∗.
Adem´as, la unci´on de ansici´on de S,δ, iene ansiciones que simulan pasos
de las dis in as FSMs Fi, con 1≤i≤n, pues es ´a de inida de la siguien e o ma:
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 nue o, una con igu aci´on (q1, B1, . . . , qn, Bn) de Sse puede en ende como el
conjun o de es ados q1, . . . , qnen que es ´an las dis in as FSMs y el con enido de los
bu e s B1, . . . , Bnen ese de e minado ins an e. Desde una de sus con igu aciones,
el sis ema puede ansi a a o as con igu aciones con li e ales dis in os de (como
mucho hab ´a nde es e ipo), aquellas que esul an de a anza un paso en la ejecu-
ci´on de cada una de las m´aquinas que no engan su bu e de lec u a ac´ıo (y que
su unci´on de ansici´on les pe mi a a anza ), y de modi ica los bu e s adecuada-
men e con espec o a lo que dic a es a ansici´on. Pe o ambi´en hay o o ipo de
ansiciones: las asociadas a pasos en los cuales cada FSM consume de su bu e
co espondien e, es deci , a anza sin consumi ning´un li e al.
Adem´as, ecupe amos el concep o de con igu aci´on de acep aci´on que ya en´ıamos
en el caso de sis emas con ´unicamen e 2 m´aquinas: nues o sis ema S iene un con-
jun o de es ados inales QF⊆Q1∪Q2∪. . . ∪Qnde o ma que una con igu aci´on
(q1, B1, q2, B2, . . . , qn, Bn) es de acep aci´on qi∈QFpa a alg´un ´ındice i∈ {1, . . . , n}.
De igual mane a, la o ma en que es os sis emas econocen palab as es la misma
que la que usaban sus an´alogos con ´unicamen e dos m´aquinas y que explicamos
en 3: conside a emos que un sis ema acep a una palab a si una con igu aci´on de
acep aci´on es alcanzable as comenza en la con igu aci´on inicial que su ge de ene
a cada FSM en su es ado inicial y odos los bu e s ac´ıos, excep o el de la (sin
p´e dida de gene alidad) p ime a m´aquina, que con iene dicha palab a.
En es os sis emas el en´omeno de p oli e aci´on de los ou pu s es oda ´ıa m´as
cla o: adem´as de lo que ocu ´ıa en el caso con ´unicamen e dos m´aquinas, que aqu´ı
ambi´en se da (pues seguimos pudiendo gene a ou pu s sin consumi inpu s), po
cada ansici´on de una m´aquina se es ´a consumiendo un li e al (a lo sumo), mien as
que po encialmen e se pod ´ıan gene a nli e ales como ou pu , lo cual hace que se
puedan gene a muchos m´as ou pu s que los inpu s que se consumen.
De hecho, podemos ene una si uaci´on en la cual haya m´aquinas que solo e-
ansmi en lo que les llega a o a m´aquina. Po ejemplo, si F1quisie a manda le
dos li e ales, AB, a F2, pod ´ıa u iliza una m´aquina in e media ia F3:F1manda ´ıa
AaF2yBaF3, y despu´es F3 e ansmi i ´ıa esa Bpa a que le llega a a F2. De
es a o ma, es a ´ıamos consiguiendo manda mensajes con m´as de un li e al de F1
aF2sin que nunca a˜nadamos m´as de un li e al a cada bu e en cada ansici´on, lo
cual nos indica que el en´omeno de p oli e aci´on de los ou pu s es comple amen e

Cap´ı ulo 5 - De inici´on gene al de los sis emas 17
inhe en e a la de inici´on de es os sis emas, pues se puede consegui incluso con la
limi aci´on de que no se pueden gene a ou pu s sin consumi inpu s.
De es a o ma, al se la p oli e aci´on de los ou pu s un en´omeno an inhe en e
a es e ipo de sis emas, no nos debe ´ıa moles a el hecho de que una FSM se pueda
manda mensajes ambi´en a s´ı misma (que en p incipio pod ´ıa no pa ece la mejo
opci´on), pues siemp e pod ´ıamos in oduci una m´aquina in e media ia con el mismo
p op´osi o (como comen amos en el p´a a o an e io ). Po an o, no end ´ıa sen ido
limi a que una m´aquina no se pueda en ia mensajes a s´ı misma.
A la is a de lo an e io , queda cla o que la ´unica o ma de e i a la p oli e aci´on
de los ou pu s en es e ipo de sis emas es que cada ansici´on gene e a lo sumo un
ou pu cada ez que consigue un inpu . Es o se da ´ıa si δi:Qi×Ii−→ Qi×
O?
in unciona de o ma que pa a cada ansici´on δi(qi, α)=(q0
i, α1, α2, . . . , αn) a
lo sumo una de las p oducciones α1, . . . , αnes dis in o de . La ´unica mane a de
consegui e i a el en´omeno de p oli e aci´on de los ou pu s se ´ıa po an o hace
es a modi icaci´on de nues a de inici´on.
Po ello, al se inhe en e a es os sis emas el en´omeno de p oli e aci´on de los
ou pu s, podemos modi ica lige amen e la de inici´on de las FSMs que usamos, de
o ma que sean m´as c´omodas de u iliza . En ez de conside a que la unci´on de
ansici´on de la m´aquina Fies δi:Qi×Σ?−→ Qi×Σ?n, podemos conside a
equi alen emen e δi:Qi×Σ?−→ Qi×(Σ∗)n, lo cual nos simpli ica ´a algunos
azonamien os en cap´ı ulos enide os. En ealidad es o es simplemen e una ex ensi´on
de los a gumen os que comen ´abamos a la ho a de de ini sis emas con solo dos
FSMs, y que demos amos con mayo o malidad en el eo ema 4.2, y po an o no
c eemos que sea necesa io incidi m´as en ello.
No emos asimismo que es e ipo de sis emas son Tu ing comple os, pues ya
hemos p obado en el cap´ı ulo an e io que una subclase suya, en la que es ingimos
el n´ume o de m´aquinas a ´unicamen e 2, ya es Tu ing comple a (como imos en el
eo ema 4.2).
5.1. Sis emas con bu e s aco ados
Pa a pode segui es ableciendo compa a i as que nos ayuden a comp ende qu´e
ca ac e ´ıs icas de los sis emas de FSMs en comunicaci´on son los que ealmen e le
dan su g an exp esi idad, amos a es udia o a modi icaci´on, en la que es a ez
hay una limi aci´on en cuan o a la memo ia que el sis ema puede usa .
De inici´on 5.2. Decimos que un sis ema de FSMs en comunicaci´on S= (F1, F2, . . . , Fn)
es un sis ema con bu e s aco ados si exis e una cons an e Mde mane a que
en cada una de las con igu aciones (q1, B1, q2, B2, . . . , qn, Bn)alcanzables de S, el
ama˜no de cada bu e es a lo sumo M, es deci , |Bi| ≤ M∀1≤i≤n.
Es a limi aci´on pod ´ıa pa ece excesi a una ez que nos damos cuen a de que en
ealidad, dada la capacidad ini a de los bu e s, en ealidad es e ipo de sis emas
solo pueden ecibi inpu s de una longi ud aco ada po M(o Mn en caso de que
Cap´ı ulo 5 - De inici´on gene al de los sis emas 18
dis ibuy´e amos de alguna o ma dichas ins ancias sob e los cuales el sis ema se
ejecu a en los di e en es bu e s). Es o ha ´ıa que los ´unicos lenguajes que se pudie an
econoce con es e ipo de sis emas ue an una subclase de los lenguajes ini os, un
es adio muy pob e en la je a qu´ıa de Chomsky. Pa a e i a es a si uaci´on un an o
indeseable, pues el hecho de que las m´aquinas es ´en en comunicaci´on no a˜nadi ´ıa
nada a su capacidad exp esi a, amos a hace una peque˜na modi icaci´on. Podemos
conside a que hay una m´aquina F0que es la que ecibe los inpu s del sis ema,
y po an o su bu e no es ´a aco ado, es una FSM no mal. Pe o si dejamos que
es a m´aquina pa icipe en la comunicaci´on con el es o de m´aquinas, ealmen e la
hip´o esis de que los bu e s es ´an aco ados no end ´ıa ya mucho sen ido, pues se
pod ´ıa usa el de F0, que no lo es. Po an o, debemos man ene a F0al ma gen
de es as comunicaciones. Podemos impone que lo ´unico que haga F0sea en ia
inpu s poco a poco a (sin p´e dida de gene alidad) F1, siemp e que B1no es ´e lleno,
y que F0no in e ac ´ue de ninguna o a mane a den o del sis ema. En conc e o,
no puede ecibi mensajes de ninguna m´aquina. De es a o ma, queda cla o que
es amos espe ando la es icci´on de los bu e s aco ados: odos los c´ompu os que
hace Su ilizan solo los bu e s aco ados; mien as que el uco de a˜nadi F0no mejo a
las ca ac e ´ıs icas de S, sino que solo pe mi e que adem´as se p ocesen palab as de
longi ud a bi a ia como inpu , lo cual es bas an e m´as azonable pa a un modelo
de c´ompu o.
Cap´ı ulo 6
Sis emas donde los ou pu s no
p oli e an
Si educimos la capacidad de comunicaci´on de nues os sis emas de FSMs no
pe mi iendo que p oli e en los ou pu s como en las si uaciones an e io es, iene sen-
ido pensa que la exp esi idad de es os sis emas cae ´a, y puede que no es ´en como
en el caso an e io a la misma al u a que las m´aquinas de Tu ing en la je a qu´ıa
de Chomsky. Pe o ampoco pie den demasiada exp esi idad, pues pueden econo-
ce lenguajes que no son incon ex uales, como el de las palab as del ipo w#w, con
w∈Σ∗pa a alg´un al abe o no i ial, como po ejemplo Σ = {0,1}(lo cual e emos
en m´as de alle a con inuaci´on). Es o nos sugie e busca un es adio in e medio en e
los au ´oma as con pila y las m´aquinas de Tu ing, como los au ´oma as linealmen e
aco ados (LBA po sus siglas en ingl´es). En es e caso, es a in uici´on a a se co-
ec a, pues a a exis i una equi alencia de exp esi idad en e los LBA y nues os
sis emas de FSMs donde los ou pu s no p oli e an.
Reco damos b e emen e la de inici´on de un LBA:
De inici´on 6.1. Se dice que F= (Q, Γ, [, q0, QF, δ)es un LBA si es una m´aquina
de Tu ing (con es ados Q, al abe o Γ, s´ımbolo de blanco [, es ado inicial q0, es ados
de acep aci´on QFy unci´on de ansici´on δ:Q×Γ−→ Q×Γ×{←,→}) de o ma
que a lo la go de oda la ejecuci´on p ocesa un inpu solo u iliza una can idad de
posiciones de su cin a que es lineal en el ama˜no de dicho inpu .
Es deci , an e un inpu de ama˜no n, un LBA solo puede u iliza una can idad
O(n) de posiciones de su cin a; y po lo dem´as se compo a como una m´aquina
de Tu ing usual. En conc e o, se suelen usa s´ımbolos delimi ado es como `,aen
ambos ex emos de la cin a pa a que quede cla o que la can idad de cin a que se
puede usa es ´a aco ada desde el p incipio. Se puede consul a m´as sob e ellos en,
po ejemplo, el cap´ı ulo 9.3 de [17].
6.1. Ejemplo de uncionamien o
Vis a la an e io in uici´on sob e en qu´e ni el de la je a qu´ıa de Chomsky pod ´ıan
si ua se los sis emas de FSMs en los cuales los ou pu s no p oli e an, conside amos
´u il desa olla m´as el ejemplo an e io pa a e m´as en de alle un ejemplo en el
cual la comunicaci´on que se es ablece en e dos FSMs sencillas es su icien e pa a
econoce un lenguaje un an o complejo, que no es incon ex ual.
19
Cap´ı ulo 6 - Sis emas donde los ou pu s no p oli e an 20
P oposici´on 6.2. El lenguaje L=w#w:w∈ {0,1}∗no es incon ex ual, pe o
puede se econocido po un sis ema de FSMs en comunicaci´on donde los ou pu s
no p oli e an.
Demos aci´on. Demos amos los dos ase os po sepa ado:
Lno es incon ex ual. Lo demos amos con una aplicaci´on del lema del bombeo.
Suponiendo que L ue a incon ex ual, sea nes la cons an e del lema del bom-
beo de L. Conside ando la palab a 0n1n#0n1n∈L, end ´ıa que admi i una
descomposici´on 0n1n#0n1n=u wxy, con | wx| ≤ n,| x| ≥ 1. Demos a e-
mos que u 2wx2y /∈Lpa a cualquie a de es as descomposiciones (llegando po
an o a una con adicci´on). Como # no se puede duplica sin que la palab a
salga de L, enemos 3 opciones:
1. # ∈w. En ese caso, como | wx| ≤ n, enemos que = 1a,x= 0b, donde
al menos uno de en e aybes es ic amen e posi i o po se | x| ≥ 1.
Si a > 0, en u 2wx2yse descompensa ´an los unos en la palab a de la
izquie da; y si b > 0, los ce os en la de la de echa. De ambos modos,
u 2wx2y /∈L.
2. # es ´a en uo m´as a su izquie da. En onces en u 2wx2yse ´a o zosamen-
e m´as la ga la palab a de la de echa, pues solo se bombea en ella. Y
necesa iamen e u 2wx2y /∈L.
3. # es ´a en yo m´as a su de echa. Es una si uaci´on an´aloga al pun o an e-
io .
Pe o, de hecho, podemos encon a un sis ema de FSMs en el cual los ou pu s
no p oli e an y que econoce es e lenguaje. Nues o sis ema se ´a S= (F1, F2).
F1i ´a econociendo las le as de la p ime a palab a, una a una, e i ´a con i -
mando que es ´an en el mismo o den en la segunda palab a con la ayuda de
F2, que i ´a esal ando las le as con las que debe ´ıan coincidi . Un ejemplo de
m´aquinas que pod ´ıan hace es a a ea se ´ıan las siguien es:
1. M´aquina F1: lo p ime o que hace es inse a [pa a simboliza el in de las
palab as. Su uncionamien o es el siguien e: hace un ba ido del bu e has a
que econoce la p ime a le a (la de despu´es de [), y en a en un es ado especial
donde la ecue da, y la qui a del bu e . Espe a has a que F2le manda una
le a con ba a a iba (que se ´an nue os li e ales del al abe o en los cuales nos
apoya emos en la cons ucci´on), que es la con i maci´on de que despu´es de #
ha enido esa le a. Si coincide con lo que eco daba, uel e a empeza el ciclo,
has a que los bu e s se ac´ıan, y en ese momen o econoce ´ıa [#[y acep a ´ıa.
Una e si´on g ´a ica de la implemen aci´on la podemos encon a en 6.1.
Cap´ı ulo 6 - Sis emas donde los ou pu s no p oli e an 27
sis emas no pe enece a ning´un ni el in e io de la je a qu´ıa de Chomsky pues, como
amos a demos a , pueden simula cualquie LBA. Po an o, son comple os den o
de los au ´oma as dependien es del con ex o. Veamos aho a es a demos aci´on.
Cabe des aca que en es e caso u iliza emos una de inici´on un an o dis in a de
los LBA, pues hay una de inici´on equi alen e que es inge la can idad de cin a que
puede usa un LBA a ´unicamen e la que ocupa su inpu inicial. Es a e si´on, en la
cual no pe mi imos una can idad lineal de cin a ex a, es equi alen e, en ´e minos
de capacidad de c´ompu o, a la que p opusimos an e io men e al de ini los LBAs
como consecuencia del Teo ema del linea speedup en m´aquinas de Tu ing (se puede
consul a en [17], cap´ı ulos 9.3, 12.2).
Teo ema 6.5. Cualquie LBA puede se simulado po un sis ema de FSMs en
comunicaci´on donde los ou pu s no p oli e an.
Demos aci´on. Sea F= (Q, Σ, [, q0, QF, δF) un LBA. Vamos a de ini un sis ema
S= (F1, F2) de FSMs donde los ou pu s no p oli e an que simule F.F2se ´a una
m´aquina muy sencilla, que simplemen e de uel e odo li e al que le llega. Pod ´ıamos
ep esen a la del siguien e modo que nos mues a la siguien e igu a:
qx/x (∀x)
Figu a 6.7: Rep esen aci´on g ´a ica de F2.
La m´aquina F1lle a ´a oda la complejidad de simula F. Como Fes esencial-
men e una m´aquina de Tu ing usual, iene una cin a, que in en a emos man ene
en B1. Pe o F iene adem´as un cabezal que puede modi ica li e ales de cualquie
posici´on de la cin a, mien as que F1solo puede oma li e ales desde el p incipio
de su bu e B1. Es o gene a una di icul ad, pe o que se sol en a de mane a sencilla,
como usualmen e en es as si uaciones: i e ando sob e odo el bu e B1cada ez que
Fd´e un paso. De es a mane a, aunque de una o ma un poco cos osa, podemos
simula cada mo imien o de Fcon la gene aci´on de un nue o bu e B1, que se ´a la
cin a de Fen el siguien e ins an e de iempo.
Adem´as, a la ho a de simula es a cin a, apa ecen cie as di icul ades. La p ime a
es la de simula el cabezal de F. Lo sol en a emos simplemen e in oduciendo m´as
li e ales: po cada γ∈Σ, el nue o li e al ¯γ∈Γ del al abe o de Ssigni ica ´a que en
el bu e hay una γy adem´as en el cabezal es ´a jus o en esa posici´on.
Se nos p esen a ambi´en la di icul ad de que el cabezal de Fpuede a anza
hacia la izquie da y a la de echa en la cin a, mien as que nues a m´aquina F1solo
puede lee su bu e en una di ecci´on (digamos que de izquie da a de echa). La
idea pa a sol en a es o es simplemen e e asa un ciclo odas las decisiones de F1,
pues as´ı nunca oma emos decisiones inco ec as del siguien e ipo: si en´ıamos α¯
β
y enemos que simula un mo imien o a la izquie da del cabezal en una ansici´on
del ipo δ(q, β) = (q0, γ, ←), es os li e ales end ´ıan que pasa a se ¯αγ; pe o solo
nos damos cuen a de que α end ´a el cabezal encima una ez que hemos isi ado

Cap´ı ulo 6 - Sis emas donde los ou pu s no p oli e an 28
βy hemos is o que ella s´ı iene el cabezal encima. Un esquema isual de es as
p oducciones a asadas se ´ıa el siguien e (a
ideno a el i-´esimo ca ´ac e de la cin a
en el ins an e , y las lechas discon inuas deno an con la lec u a de qu´e li e al se
gene an o os li e ales):
a0
0a0
1a0
2a0
3a0
4a0
5
a1
0a1
1a1
2a1
3a1
4a1
5
a2
0a2
1a2
2a2
3a2
4a2
5
Figu a 6.8: Ejemplo explica i o de en qu´e momen o se lle a a cabo cada p oducci´on.
Adem´as enemos que consegui es e e aso en la ejecuci´on sin que p oli e en
los ou pu s, lo cual no es inmedia o de consegui en una p ime a ap oximaci´on al
p oblema. Es o se puede soluciona in oduciendo un ca ´ac e # que indique el in
de la cin a de Fen nues os bu e s (es deci , que sepa e los bu e s que se e ie en
a di e en es ins an es de iempo), lo cual sigue la idea de los LBA de delimi a la
memo ia que podemos u iliza .
Con es as ideas en men e, pasemos a la implemen aci´on de mane a m´as conc e a
de la m´aquina F1. Lo p ime o es comen a que el al abe o que usa ´a el sis ema S
se ´a, como an es se indicaba: Γ := Σ ∪{¯γ:γ∈Σ}∪{#}.
Pa a cada es ado qi∈Qde F end emos un clus e de es ados en F1que si-
mula ´an un ba ido de la cin a de Fmien as es ´a en el es ado qi, cuyos es ados
deno a emos qi(adem´as de m´as sub´ındices pa a indica la unci´on de esos es ados
den o del clus e ). En cada uno de es os clus e s enemos que implemen a la idea
an e io de e asa la p oducci´on de ou pu s un ciclo, as´ı que end emos que ene
un es ado di e en e pa a cada li e al de Γ pa a eco da cu´al es el li e al que aca-
bamos de e . Adem´as, enemos que consegui simula las ansiciones de F. Po
ejemplo, si en Fhay una ansici´on de qiaqjcuando el cabezal e una A, nues a
m´aquina F1, en su clus e ela i o a qi, end ´a una ansici´on di e en e cuando ea
¯
A, pues ansi a ´a hacia una egi´on di e en e del clus e en la cual eco da emos que
el siguien e es ado al que a a i Fes qj. De es a o ma, cuando le llegue la siguien e
#, F1 ansi a ´a hacia el clus e ela i o a qj, y comenza ´a de nue o a ba e la
cin a de Fleyendo de su bu e .
Pa a pode cumpli es o, cada clus e qi end ´a un conjun o de es ados qγ
i, con
γ∈Σ∪ {#}, de o ma que ejecu an la c eaci´on del nue o bu e an es de que se
haya isi ado la posici´on donde es ´a el cabezal lec o (es deci , an de ol iendo
exac amen e lo que leen, pe o un ciclo m´as a de). Pos e io men e, al e el cabezal,
hemos de dis ingui si las di e sas ansiciones de Fen qimue en el cabezal a la
Cap´ı ulo 6 - Sis emas donde los ou pu s no p oli e an 29
izquie da o a la de echa, pues se nos gene a ´a una es uc u a di e en e de es ados
en cada caso.
Po ejemplo, si en F enemos una ansici´on que mue e el cabezal lec o hacia
la izquie da, del ipo que nos mues a la siguien e igu a:
qiqj
a/b, ←
Figu a 6.9: Rep esen aci´on g ´a ica de un ejemplo de ansici´on que mue e el cabezal
a la izquie da.
Tenemos po an o que ene una es uc u a de es ados den o del clus e asocia-
do a qique pueda sol en a es a si uaci´on. Tend emos pa a ello un es ado q0
i→jque
isi a emos jus o cuando hayamos is o el cabezal con una A, y que nos ayuda ´a a
ansi a hacia una zona del clus e donde eco damos que el siguien e es ado que
isi a ´a Fes qj. Una ez isi ado q0
i→j, nos encon amos con o a egi´on del clus e
donde lo ´unico que hacemos es copia el bu e pa a la siguien e i e aci´on, al igual
que hac´ıamos con los es ados del ipo qγ
i. Po eso llamamos a es os es ados qγ
i→j,
pe o es a ez ´unicamen e con γ∈Σ, pues la llegada de una # nos ha ´a ansi a
hacia el clus e asociado a qj. Suponiendo, po simplicidad pa a la ep esen aci´on
g ´a ica, que Σ = {a, b}(una ez is o el diag ama queda ´a cla o que es sencillo
gene aliza lo a un al abe o con m´as li e ales), pod ´ıamos plasma es as ideas sob e
el clus e de qide la o ma que nos indica la igu a 6.10.
q#
i
de o os
clus e s
qa
i
qb
i
q0
i→j
qa
i→j
qb
i→j
q#
j
clus e 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
Figu a 6.10: Rep esen aci´on g ´a ica de la implemen aci´on de un clus e simulando
ansiciones que mue en el cabezal hacia la izquie da.
Cap´ı ulo 6 - Sis emas donde los ou pu s no p oli e an 30
Y, en cambio, si la ansici´on de Fmue e el cabezal a la de echa, enemos que
in oduci algunos es ados m´as pa a eco da los li e ales que emos du an e es e
mo imien o. Supongamos en onces que enemos en F enemos la ansici´on en e
qi, qj∈Q, del ipo de la igu a siguien e:
qiqj
a/b, →
Figu a 6.11: Rep esen aci´on g ´a ica de un ejemplo de ansici´on que mue e el cabezal
a la de echa.
En onces en F end emos que ene una es uc u a del es ilo de la mos ada en la
igu a 6.12 den o del clus e ela i o a q1, que es bas an e simila a la an e io , pe o
donde in oducimos algunos es ados m´as q1,γ
i→j, con γ∈Σ pa a eco da los li e ales
que emos jus amen e al llega al cabezal (de nue o supond emos Σ = {a, b}po
simplicidad del diag ama):
q#
i
de o os
clus e s
qa
i
qb
i
q0
i→j
q1,a
i→j
q1,b
i→j
qa
i→j
qb
i→j
q#
j
clus e 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
Figu a 6.12: Rep esen aci´on g ´a ica de la implemen aci´on de un clus e simulando
ansiciones que mue en el cabezal hacia la de echa.
Na u almen e, desde un es ado qide Fpod ´ıa da se el caso de que hubie a
ansiciones a m´as de un es ado del ipo qjen los ejemplos an e io es. Es o ha ´ıa
Cap´ı ulo 6 - Sis emas donde los ou pu s no p oli e an 31
que nues o clus e asociado a qi ue a m´as g ande, ya que pa a cada ansici´on de
qiaqj, el clus e debe ´ıa con ene una es uc u a de es ados qi→j. Es deci , den o
de un mismo clus e , end emos que ene an as es uc u as del ipo qi→jcomo
ansiciones enga Fen qi.
De es a o ma, en el clus e del es ado qide F enemos una columna de es ados
en los cuales no hemos is o oda ´ıa la posici´on del cabezal (los qγ
i, despu´es una
se ie de es ados (un conjun o de es ados po cada ansici´on salien e de qien F)
que manejan el a amien o del li e al con el cabezal y la ansici´on de F(los q0
i→j,
q1,γ
i→j), y una se ie de columnas de es ados ( ambi´en una po cada ansici´on de qi)
que ecue dan a qu´e es ado ansi a Fy, po an o, cu´al es el siguien e clus e al
que i ´a F1(los es ados del ipo qγ
i→j).
As´ı podemos i simulando ansiciones de F, que modi ican un pa de posiciones
de la cin a, con un eco ido den o de uno de los clus e s de F1, que gene a un
nue o bu e simulando la cin a de F, y se la en ´ıa a F2.F2, po su pa e, een ´ıa
el bu e a F1pa a que pueda e ec ua la siguien e ansici´on.
Es impo an e hace hincapi´e en el inicio de odo es e p ocedimien o: al p incipio,
el inpu de Fse pone en el bu e B1(sin ninguna modi icaci´on), y el es ado inicial
de F1es q#
0( eco demos que el es ado inicial de Fe a q0). As´ı, lo p ime o que
ha ´a F1se ´a gene a una #, lo cual le ayuda ´a a dis ingui ese bu e del que se
co esponde ´a al siguien e es ado de la cin a de F. Despu´es segui ´a a ando los
li e ales de B1con o al no malidad, empezando en el clus e de q0, cla o.
Y simula el c i e io de acep aci´on de F ambi´en es sencillo: simplemen e enemos
que hace que (qi, q)∈Q1×Q2sea de acep aci´on siemp e que qi ep esen e en F1
un es ado inal de F, es deci , qi∈QF⊆Q.
De es a o ma, hemos hecho una educci´on del LBA Fa un sis ema de FSMs en el
cual los ou pu s no p oli e an, como hemos comp obado a la ho a de cons ui los.
Adem´as, en el sis ema de FSMs que hemos cons uido, el n´ume o de es ados es
polin´omico con espec o a los de F:
|QF1|= #clus e s ·#es ados po clus e
≤ |QF|·(|QF|+ 1) ·(|ΣF|+ 1) + 1 + |ΣF|+ 1∈ O|QF|2
Es o demues a que la c eaci´on del sis ema de FSMs en unci´on de Fse puede
hace con una can idad de es ados polin´omica espec o al ama˜no de F. Adem´as,
la educci´on, en cuan o a iempos de ejecuci´on, ambi´en es polin´omica: si enemos
un inpu de longi ud ny, pa a p ocesa dicho inpu , Fda kpasos; en onces nues o
sis ema S, po cada uno de es os kpasos eco e ´a la cin a en e a de Fdos eces
(una se ´a po un eco ido de F1y o a po el de F2). Pe o como Fes un LBA, el
ama˜no de la cin a siemp e es ´a aco ado po n. Es deci , el sis ema Sda ´a O(nk)
pasos en su ejecuci´on. Po an o, podemos a i ma que la educci´on es polin´omica y
no se a˜nade po an o un sob ecos e ese˜nable.
Cap´ı ulo 7
Sis emas con bu e s aco ados
O o caso que podemos es udia es el de un sis ema de FSMs en comunicaci´on
en el cual los bu e s, po alguna az´on, ienen ama˜no aco ado desde el p incipio,
como de inimos en el apa ado 5.1. Es o supone una limi aci´on simila a la es udiada
en el caso de que los ou pu s no p oli e a an en el sen ido de que es amos limi ando
la exp esi idad de nues o sis ema. En el caso de que los ou pu s no p oli e a an ya
es udiamos que el sis ema dejaba de se Tu ing comple o, y se quedaba en un es adio
un poco an e io de la je a qu´ıa de Chomsky, el de los lenguajes dependien es del
con ex o. En es e caso, amos a e sin mucha di icul ad que podemos comp oba
que la limi aci´on de la exp esi idad es mucho m´as po en e, y es e ipo de sis emas se
an a queda en lo m´as bajo de la je a qu´ıa, en los lenguajes egula es. Es o se debe
a que la in o maci´on que po encialmen e puede ene el sis ema es en cualquie caso
ini a, pues las FSMs in oluc adas lo son, y los bu e s ambi´en. Es o con as a con
el caso an e io po una su ileza: cuando no p oli e aban los ou pu s, la in o maci´on
es aba aco ada dependiendo del ama˜no inicial del inpu , pe o como el ama˜no inicial
del inpu no es ´a aco ado de an emano, la can idad de in o maci´on que en´ıan esos
sis emas es mucho mayo que la de los sis emas que pasamos a es udia aho a.
Vamos a p ocede a simula un sis ema de FSMs con bu e s aco ados median e
un au ´oma a ini o. Es o demos a ´ıa que nues o sis ema de FSMs como mucho
puede econoce lenguajes egula es. Pe o como, en conc e o, el sis ema es ´a o ma-
do po FSMs, que son au ´oma as ini os, ambi´en el sis ema puede simula cualquie
au ´oma a ini o, y es o demues a la equi alencia en e ambos modelos. La conclu-
si´on cla a es que a˜nadi bu e s aco ados a unas FSMs pa a que se comuniquen en e
ellas no a˜nade en ning´un caso exp esi idad.
Teo ema 7.1. Cualquie sis ema de FSMs en comunicaci´on con bu e s aco ados
puede se simulado po un au ´oma a ini o.
Demos aci´on. Sea S= (F0, F1, F2, . . . , Fn) un sis ema de FSMs en comunicaci´on
con bu e s aco ados, con bu e s B0, B1, B2, . . . , Bn. Reco demos que es o signi ica
que exis e un Mp e ijado de o ma que la longi ud de odos los bu e s (excep o B0,
que co esponde a la m´aquina especial F0seg´un de inimos en la secci´on 5.1) es ´a
siemp e aco ada po M. Digamos que el al abe o com´un de Ses Σ, y con ´el de inimos
Σ≤M:= {w∈Σ∗:|w| ≤ M}, que nos ayuda ´a a simpli ica las exp esiones ela i as
a los bu e s. Adem´as, las m´aquinas se ´an Fi= (Qi, Ii, Oi, q0
i, δi), con 0 ≤i≤n, y
Ii, Oi⊆Σ, na u almen e.
De inamos aho a el au ´oma a ini o F= (Q, Σ, q0, QF, δ) que los simula ´a.
La cla e es ´a en hace Q=Q1×Σ≤M×Q2×Σ≤M× ··· × Qn×Σ≤M, que
32

Cap´ı ulo 7 - Sis emas con bu e s aco ados 33
simula ´a po comple o el es ado del sis ema Sde la siguien e o ma: el es ado
(q1, α1, q2, α2, . . . , qn, αn)∈Qsimboliza ´a que F1es ´a en el es ado q1,F2, en q2,
y as´ı sucesi amen e; y que el bu e B1 iene po con enido la palab a α1,B2 iene
la palab a α2, y as´ı sucesi amen e. No emos que algunas de las posiciones de los
bu e s pueden es a ac´ıas, pues no necesa iamen e |αi|=M, sino que en gene al
end emos |αi| ≤ Mpo se palab as de Σ≤M.
Como emos, el al abe o se ´a Σ, el mismo que en´ıa S, lo cual es necesa io pa a
que Fpueda acep a los mismos s´ımbolos. Pa a cada s´ımbolo γ∈Σ que ma que
una ansici´on de F, que emos que signi ique que la m´aquina F0in oduce en ese
ins an e el siguien e li e al del inpu inicial, que es a ez se ´a γ, dej´andolo en el
inal del bu e B1, cla o. Pe o en cada es ado de Fhab ´a m´as ansiciones: aquellas
que pueda da el sis ema Ssin consumi li e ales del inpu (y po eso Fconsumi ´a
´unicamen e ), y que e lejan que una m´aquina Fi, con i≥1, ha dado un paso en
su ejecuci´on.
Nos al a de ini la unci´on de ansici´on δde F, lo cual es sencillo a pa i de las
ideas an e io es. Tenemos que en ende c´omo eacciona an e los di e en es li e ales
de Σ, as´ı que pasamos a de ini es as ansiciones.
Supongamos que es amos en un es ado a bi a io (q1, α1, q2, α2, . . . , qn, αn)∈Q.
Veamos cu´ales son las di e en es ansiciones que iene es e es ado en F.
Pa a los li e ales γ∈Σ, enemos que a˜nadi γaB1en caso de que es e bu e
no es ´e lleno.
|α1|< M =⇒δ((q1, α1, q2, α2, . . . , qn, αn), γ)=(q1, α1+γ, q2, α2, . . . , qn, αn)
Pa a las ansiciones que se oman con , enemos que simula una ansici´on
de la m´aquina Fi, pa a cada 1 ≤i≤n. Es a ansici´on depende ´a de head(αi)
(en caso de que el bu e Bino es ´e ac´ıo). Digamos que la ansici´on es la
siguien e: δi(qi, head(αi)) = (q0
i, β1, β2, . . . , βn), donde q0
i∈Qies el es ado de
llegada y βj∈Σ?es lo que se a˜nade a Bjpa a 1 ≤j≤n( eco demos que
F0no pa icipa en la comunicaci´on, as´ı que po simplicidad la omi imos). La
ansici´on se ´a posible en caso de que ninguno de los bu e s exceda su ama˜no
al a˜nadi es os li e ales, lo cual podemos exp esa de la siguien e o ma:
|α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), )
Po ´ul imo, comen a el es ado inicial de la m´aquina F. Simplemen e se ´ıa el
es ado (q0
1, , q0
2, , . . . , q0
n, ). Y na u almen e, los es ados de acep aci´on de Fse ´an
aquellos en los cuales (q1, q2, . . . , qn) sea una con igu aci´on de acep aci´on de S.
Con es e sencillo p ocedimien o queda cla o que el au ´oma a F( ini o) que hemos
de inido simula el compo amien o de S, pues simula cada uno de los pasos que puede
oma en cada una de sus con igu aciones.
Cap´ı ulo 7 - Sis emas con bu e s aco ados 34
Adem´as la educci´on es polin´omica con o me c ece el ama˜no de las m´aquinas
del sis ema S: si S iene kes ados (es deci , |Q1|+|Q2|+. . . +|Qn|=k), en onces
F iene, a lo sumo, con una ap oximaci´on na¨ı e, (kM)nes ados, lo cual es una
can idad polin´omica en k, supues o que el n´ume o nde m´aquinas que con o man S
y la cons an e que aco a los bu e s Mson conocidas de an emano.
Cap´ı ulo 8
Sis emas con bu e s sin o den
O a modi icaci´on posible de los sis emas de FSMs en comunicaci´on esidi ´ıa en
modi ica el uncionamien o de los bu e s. Has a aho a, siemp e han es ado imple-
men ados en o ma de cola, de o ma que los li e ales siemp e quedaban o denados
con o me a su momen o de llegada. Aho a amos a es udia la si uaci´on en la cual
es e o den se pe die a, po ejemplo po las ca ac e ´ıs icas ´ısicas de nues o sis ema,
que pod ´ıa no sopo a es uc u as de ipo cola o simplemen e es uc u as o dena-
das, o po que el p o ocolo usado no pe mi e asegu a que se espe e el o den de
llegada a los bu e s. Se nos plan ea en onces la siguien e modi icaci´on: si el con e-
nido de los bu e s puede se ep esen ado po mul iconjun os en luga de colas, es
deci , es os bu e s pe enecen a Σ⊕( eco demos que X⊕es la clase de mul iconjun-
os ini os con elemen os en X) en ez de a Σ∗(donde Σ es el al abe o del sis ema),
¿qu´e ca ac e ´ıs icas ienen es os sis emas?
Lo p ime o que amos a hace es de ini c´omo e olucionan es e ipo de sis e-
mas, pues las eglas que de inimos en la secci´on 5no uncionan. Sin emba go, una
lige a modi icaci´on de c´omo se compo an las unciones de ansici´on que hab´ıamos
es udiado an e io men e nos p opo ciona un ma co pa a es e ipo de sis emas.
De inici´on 8.1. Decimos que S= (F1, F2, . . . , Fn)es un sis ema de FSMs en
comunicaci´on sin o den en el caso de que las dis in as FSMs gene an ou pu s
en Σ⊕(en ez de en Σ∗, como e a habi ual), es deci , δi:Qi×Σ?−→ Qi×(Σ⊕)n
pa a 1≤i≤n. Una con igu aci´on de Sse ´a una upla de Q1×Σ⊕×Q2×Σ⊕×
···×Qn×Σ⊕.
La unci´on de ansici´on en e dis in as con igu aciones de Ses δ:Q1×Σ⊕×
Q2×Σ⊕×···×Qn×Σ⊕−→ Q1×Σ⊕×Q2×Σ⊕×···×Qn×Σ⊕, que iene de inida
de la siguien e mane a:
con ains(Bi, γ)∧δi(qi, γ)=(q0
i, α1, α2, . . . , αn) =⇒
(q1, B1+α1, . . . , qi−1, Bi−1+αi−1, q0
i, e ase(Bi, γ) + αi, qi+1, Bi+1 +αi+1, . . . , qn, Bn+αn)
∈δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn)
En es e caso con ains(B, γ) es una unci´on que dice si hay alguna ocu encia del
li e al γ∈Σ en el mul iconjun o B( i ialmen e cie o si γ=), e ase(B, γ) es una
unci´on que elimina una ocu encia de γde B(lo cual pod ´ıamos en ende como
B {γ}), y + ep esen a la suma usual de mul iconjun os (si un li e al γapa ece a
eces en el mul iconjun o Ayb eces en B, en onces apa ece a+b eces en A+B).
35
Cap´ı ulo 8 - Sis emas con bu e s sin o den 36
Como has a aho a, las con igu aciones dependen de los es ados en que es ´an las
di e en es FSMs en cada ins an e, y los mul iconjun os se pueden in e p e a como el
con enido de los bu e s B1, B2, . . . , Bn, que es a ez uncionan como mul iconjun os.
La m´aquina Fi oma inpu s de Biy gene a ou pu s que se a˜naden al es o de bu e s.
Una ez is a la adap aci´on de la de inici´on de sis emas de FSMs en comunicaci´on
a es a si uaci´on, amos a es ablece una compa a i a con las edes de Pe i, pues son
los sis emas m´as conocidos que abajan con mul iconjun os, es deci , con inpu s y
ou pu s sin un o den de inido.
8.1. Exp esi idad de los sis emas con bu e s sin o den
Lo p ime o que amos a hace es comp oba que es os sis emas son en ealidad
simulables po edes de Pe i usuales. Vamos a eco da es e concep o:
De inici´on 8.2. Una ed de Pe i Nes una upla (P, T, A, M, W).Pes el con-
jun o de luga es de N,Tel conjun o de ansiciones y A⊆(P×T)∪(T×P)el
conjun o de a cos (o elaci´on de lujo en e luga es y ansiciones). En cada mo-
men o, cada luga de P iene una can idad no nega i a de okens, indicada po el
ma caje M:P−→ N. Y cada ansici´on de Tpuede consumi o gene a una can i-
dad dis in a de okens en cada uno de los luga es que se elacionan con ella a a ´es
de los a cos de A. La can idad de okens que se in e cambian con cada ansici´on
po medio de cada a co ienen de e minados po W:A−→ N.
A la is a de la de inici´on, eamos el esul ado que augu ´abamos.
P oposici´on 8.3. Cualquie sis ema de FSMs en comunicaci´on con bu e s sin
o den puede se simulado po una ed de Pe i.
Demos aci´on. Dado un sis ema S= (F1, F2, . . . , Fn), amos a cons ui una ed
de Pe i Nque lo simule. La ed de Pe i se ´a N= (P, T, A, M, W), como en la
de inici´on an e io . Supongamos que el al abe o de Ses Σ.
Po cada es ado qide cada m´aquina Fj end emos un luga en P, que deno a-
emos qj
i. Es os luga es end ´an siemp e a lo sumo un oken, y ep esen a ´an si la
m´aquina Fjes ´a en el es ado qia lo la go de la simulaci´on que hace N. Adem´as,
po cada li e al γ∈Σ y cada bu e Bj end emos ambi´en un luga , bj
γ, que end ´a
an os okens como ocu encias de γhaya en Bjen un ins an e de e minado. En
p incipio, po las ca ac e ´ıs icas de los sis emas de FSMs, es os luga es no es ´an
aco ados.
Po cada ansici´on de Fj, 1 ≤j≤n, end emos una ansici´on en N. Es deci ,
si nume amos las ansiciones de cada m´aquina Fjdesde el 1 has a j, el conjun o
de ansiciones de Nse ´a T={ j
i: 1 ≤j≤n, 1≤i≤ j}, donde j
isimula ´a la
i-´esima en ada de δj.
Queda po an o de ini las elaciones en e luga es y ansiciones, a a ´es de e-
laci´on de lujo A. Supongamos que enemos una ansici´on a bi a ia de δj, digamos
Cap´ı ulo 9
Sis emas de Mensajes Pe didos
En nues o camino explo ando di e en es e siones de nues os sis emas de FSMs
podemos isi a uno de los modelos m´as conocidos y es udiados de es e ipo. Si
suponemos que los canales de comunicaci´on que usamos (los bu e s que ayudan a la
comunicaci´on en nues o caso) no son ideales y, po an o, son suscep ibles a allos
de o ma que algunos li e ales puedan desapa ece de ellos en cualquie momen o
sin ning´un mecanismo que con ole es as p´e didas, llegamos a un concep o bas an e
simila al de los Sis emas de Mensajes Pe didos (LCS po su nomb e en ingl´es: Lossy
Channel Sys ems).
Los LCS usuales que podemos encon a en la li e a u a son un ipo de sis emas
de FSMs en comunicaci´on en los cuales hay un ipo de ansici´on adicional: en
cualquie pun o de la ejecuci´on, pueden desapa ece un conjun o de li e ales de
cualquie bu e del sis ema. Es e compo amien o es pu amen e no de e minis a: no
hay mane a de con ola lo, puede su gi en cualquie momen o y a ec a a cualquie
g upo de li e ales. Dado es e no de e minismo inhe en e a los LCS, en gene al se
suele pe mi i ambi´en que las FSMs u ilizadas sean no de e minis as (y eco demos
que no oda FSM no de e minis a se puede con e i en una de e minis a, pues
an e una misma secuencia de inpu s las FSMs no de e minis as pueden gene a
po encialmen e m´as cadenas de ou pu s di e en es que las de e minis as), lo cual los
di e encia un poco m´as de nues os sis emas de FSMs.
En gene al, un LCS puede, en cie o sen ido, simula las ejecuciones de un sis e-
ma de FSMs, pues una de sus posibles ejecuciones es aquella en la que las ansiciones
que pie den li e ales nunca se ac i an, y en conc e o es e se ´ıa el compo amien o
que ienen nues os sis emas. No obs an e, las p opiedades de ambos ipos de sis-
emas no son las mismas po que en los LCS hay muchas m´as posibles ejecuciones
en las que se pie den algunos li e ales de los bu e s. En cambio, una simulaci´on en
sen ido con a io no es posible a menos que in oduzcamos cambios en la de inici´on
de nues os sis emas (no es posible simula esas p´e didas de li e ales no de e minis-
as con nues os sis emas de FSMs usuales), pues hay p opiedades en las que ambos
modelos di ie en: po ejemplo, el p oblema de la e minaci´on (que el sis ema no
enga amas de ejecuci´on in ini as dado un inpu ) es decidible en el caso de los LCS
e indecidible en el de los sis emas de FSMs en comunicaci´on (P oblema de Pa ada).
Una o ma de hace que nues os sis emas de FSMs pudie an ene la capaci-
dad de pe de mensajes de o ma no de e minis a, como ocu e en los LCS, se ´ıa
in oduci un cie o g ado de no de e minismo en las FSMs. Po ejemplo, si pa a
cada ansici´on δ(q, α)=(q0, β) de una de las FSMs de nues o sis ema pe mi i-
mos a˜nadi ambi´en la ansici´on δ(q, α)=(q0, ), es a ´ıamos pudiendo simula es e
43

Cap´ı ulo 9 - Sis emas de Mensajes Pe didos 44
en´omeno ya que, de mane a no de e minis a, pod ´ıan no llega los mensajes a su
bu e des ino. Adem´as, es o es in oduci un no de e minismo muy con olado, as´ı
que ampoco es que el cambio haya sido excesi o. Lo in e esan e a a se la di e encia
en e p opiedades que gene an es os cambios.
Aunque pueda pa ece algo pa ad´ojico, nume osos p oblemas de decisi´on son
m´as a ables en los LCS que en el caso de los sis emas de FSMs en comunicaci´on y
las m´aquinas de Tu ing, donde esencialmen e los p oblemas son indecidibles en su
mayo ´ıa. En conc e o, un p oblema de i al impo ancia, como es el de la alcanzabi-
lidad, es decidible pa a los LCS ([2], cap´ı ulo 5) . Tambi´en es decidible el p oblema
de la ine i abilidad (dado un conjun o de es ados, ¿es ine i able que cualquie eje-
cuci´on maximal pase po alguno de dichos es ados?), que engloba el p oblema de
la e minaci´on (usando como conjun o de es ados aquellos es ados en los cuales la
ejecuci´on e mina), muy impo an e ambi´en en la eo ´ıa de au ´oma as ([21], eo-
ema 8). Tambi´en son decidibles o as p opiedades que comp ueban que a lo la go
de las ejecuciones maximales se conse an cie as p opiedades, lo cual es de u ilidad
en es e caso debido a que es impo an e ene cie os m´e odos de e i icaci´on del
uncionamien o de los sis emas que palien en cie o modo su na u aleza, que pe mi e
que los mensajes se pie dan.
No obs an e, ni mucho menos odas las p opiedades de es os sis emas son de-
cidibles: en gene al, o as como la aco aci´on (¿la can idad de li e ales que puede
habe en un canal/bu e a lo la go de cualquie ejecuci´on es ´a aco ada?) o cie as
p opiedades de jus icia, como sabe si es ine i able pasa po un cie o es ado de
con ol in ini as eces, son indecidibles ([1], eo ema 3.7).
M´as a´un: a pesa de se decidibles los p oblemas an es comen ados, como el de la
alcanzabilidad, ienen una complejidad ex emadamen e g ande. No es ´an asociados
a unciones ecu si as p imi i as ([27], eo emas 4.2, 4.4). De hecho, se puede e la
g an dis ancia a la que es ´an de es a clase de unciones con un b e e is azo a la
Je a qu´ıa de C ecimien o R´apido (Fas G owing Hie a chy): las unciones ecu si as
p imi i as es ´an asociadas a o dinales aco ados supe io men e po ω(el p ime o -
dinal nume able), mien as que los p oblemas de la alcanzabilidad e ine i abilidad
es ´an asociados al o dinal ωω.
9.1. In oduciendo jus icia en las ejecuciones
Una ez is as las p opiedades b´asicas de los LCS en gene al, amos a comp oba
que in oduci a nues os sis emas de FSMs la capacidad de hace que los mensajes se
puedan pe de de o ma no de e minis a hace que consigamos una clase es ingida
de los LCS gene ales, y es o nos a a p opo ciona alguna en aja in e esan e.
Po ejemplo, se ´ıa in e esan e in oduci cie as nociones de jus icia en es e ipo
de sis emas. Es o se debe a que el hecho de que los mensajes se puedan pe de puede
llega a deg ada bas an e la comunicaci´on en e a ias m´aquinas en una si uaci´on
eal, en la cual pod ´ıa se que la ed alla a mucho y casi ning´un mensaje se manda a.
Si u i´e amos asegu ada cie a jus icia en nues o ambien e, como que cie os com-
po amien os se ienen que da pe i´odicamen e sean cuales sean las ci cuns ancias,
Cap´ı ulo 9 - Sis emas de Mensajes Pe didos 45
pod ´ıamos al menos in en a palia los posibles allos de la ed epi iendo el en ´ıo
de los mensajes, pues la jus icia nos asegu a ´ıa que, a de o emp ano, es segu o que
los mensajes llega ´an.
Dos modelos de jus icia in e esan es que an a se de especial in e ´es son los que
se es udian en [20]. Pa a un sis ema S= (F1, . . . , Fn):
Decimos que una ejecuci´on es d´ebilmen e jus a si pa a cada m´aquina Fise
cumple que es ´a bloqueada (es deci , que dada la composici´on de su bu e
y su es ado ac ual, no puede a anza en ese ins an e) un n´ume o in ini o de
eces a lo la go de la ejecuci´on o que in ini os pasos de la ejecuci´on de Sson
pasos de Fien los que desapa ecen li e ales de su bu e .
Decimos que una ejecuci´on es ue emen e jus a si pa a cada m´aquina Fise
cumple que a pa i de un cie o paso de la ejecuci´on de SFies ´a siemp e
bloqueada o si in ini os pasos de la ejecuci´on de Sson pasos de Fien los que
desapa ecen li e ales de su bu e .
Ambos concep os b´asicamen e de lo que nos es ´an in o mando es de que, mien as
no es ´an bloqueadas, las m´aquinas an al e n´andose ela i amen e en e ellas en su
ejecuci´on, hay una cie a jus icia en e odas las m´aquinas. En la jus icia ue e
adem´as se exige que cada m´aquina no se bloquee casi nunca o que e mine en
iempo ini o su ejecuci´on, lo cual da la idea de que, en e aquellas m´aquinas que
no se bloqueen en iempo ini o, end ´a que habe g an g ado de al e nancia en las
ejecuciones. Adem´as, l´ogicamen e, si una ejecuci´on es ue emen e jus a, ambi´en es
d´ebilmen e jus a.
Veamos aho a qu´e pasa si imponemos es os sen idos de jus icia a la modi icaci´on
de los sis emas de FSMs en comunicaci´on en los cuales pe mi imos que se pie dan
mensajes. Es udia emos qu´e pasa con el p oblema de la e minaci´on imponiendo
es os concep os de jus icia: ¿ odas las amas de ejecuci´on de nues o sis ema acaban
en iempo ini o imponiendo jus icia ue e/d´ebil? La espues a es la con a ia a ¿hay
alguna ejecuci´on in ini a en la que se espe e la jus icia ue e/d´ebil?, que ambi´en
puede se i en ocasiones pa a di e en es in e p e aciones.
F1
F2
···
Fn
Bu e 1
Bu e 2
···
Bu e n
Figu a 9.1: Esquema de las comunicaciones en un
sis ema de FSMs en comunicaci´on.
Lo que podemos e es que,
po la o ma en que hemos
dise˜nado nues os sis emas de
FSMs, cada bu e solo si e co-
mo inpu de una ´unica m´aqui-
na (lo cual podemos e g ´a i-
camen e en la igu a 9.1). Es-
o hace que engamos una clase
es ingida de los LCS, que en
[20] llaman sis emas sin canales
mul iplexados.
Es o es in e esan e po que
en LCS gene ales se iene el si-
guien e esul ado:
Cap´ı ulo 9 - Sis emas de Mensajes Pe didos 46
P oposici´on 9.1 (3.1 en [20]).En LCS sin canales mul iplexados el p oblema de
la e minaci´on imponiendo jus icia ue e/d´ebil es decidible.
Po an o, en el caso de nues os sis emas de FSMs modi icados, como acabamos
de e en los p´a a os an e io es, es ´an con enidos en la subclase de los LCS sin
canales mul iplexados, podemos aplica les el eo ema 9.1 (sabiendo que, como es
sencillo comp oba , se decidible es una p opiedad que las subclases he edan). Es o
nos conduce al siguien e esul ado:
Co ola io 9.2. En los sis emas de FSMs en comunicaci´on modi icados pa a que se
puedan pe de mensajes de los bu e s de mane a no de e minis a, el p oblema de la
e minaci´on es decidible si imponemos jus icia ue e o d´ebil.
Es a p opiedad es in e esan e po que nos in o ma de que podemos in oduci
concep os de jus icia a bajo cos e (sin pe de la decibilidad de la p opiedad de
e minaci´on). Y es in e esan e in oduci la jus icia po que as´ı enemos algunas
ce ezas m´as que en el caso de que no engamos absolu amen e ning´un con ol sob e
la p´e dida de mensajes en nues o sis ema.
Cap´ı ulo 10
Complejidad de algunas
p opiedades
A pesa de que, en i ud del eo ema de Rice, odos los p oblemas de decisi´on
no i iales sob e sis emas de FSMs en comunicaci´on son indecidibles (pues lo son
pa a las m´aquinas de Tu ing), podemos es udia la complejidad de esol e alguno
de es os p oblemas en algunas de sus e siones simpli icadas que s´ı queden en el
ango de lo decidible.
10.1. El p oblema de la alcanzabilidad ini a
En es e apa ado amos a en a m´as a ondo en una de las p opiedades b´asicas: la
alcanzabilidad. Como el p oblema de la alcanzabilidad, en su e si´on gene al, esul a
indecidible, en es e caso es udia emos la alcanzabilidad ini a (que aqu´ı deno a emos
ambi´en N-alcanzabilidad, pa a que quede cla o que la limi aci´on de la ini ud iene
p e ijada po una cons an e N), que es el siguien e p oblema: dado un na u al N
y una posible con igu aci´on de nues o sis ema de FSMs en comunicaci´on S, ¿es
posible alcanza dicha con igu aci´on dando Sa lo sumo Npasos en su ejecuci´on?
De hecho, e emos el caso de que la con igu aci´on que buscamos alcanza sea una
cualquie a en la que Sacep a, plan e´andonos el p oblema ¿puede acep a Sen a lo
sumo Npasos en su ejecuci´on? Ve emos que es e p oblema de decisi´on no es sencillo
de esol e en el caso gene al, an o que esul a se un p oblema NP-comple o.
Vamos a p ocede a la demos aci´on de es e hecho.
Lema 10.1. El p oblema de la alcanzabilidad ini a en sis emas de FSMs en comu-
nicaci´on es NP.
Demos aci´on. Si enemos un sis ema de FSMs en comunicaci´on S= (F1, F2, . . . , Fn),
sabe si Salcanza ´a un de e minado es ado en menos de Npasos es un p oblema
NP: de mane a no de e minis a se puede, en caso de que haya o ma de alcanza
dicho es ado, ace a cu´al es el o den de ejecuci´on, es deci , si el siguien e paso del
sis ema se ´a ejecu a una ansici´on de F1, de F2. . . o de Fn. Dado es e o den de
ejecuci´on, es ya i ial comp oba que unciona: simplemen e amos ejecu ando las
ansiciones en F1, F2, . . . , Fny modi icando los bu e s co espondien es, y al inal
comp obamos si el es ado al que hemos llegado es el espe ado. Es a comp obaci´on
es cla amen e polin´omica, de hecho O(N) si implemen amos con enien emen e las
ope aciones de inse ci´on y ex acci´on de elemen os de los bu e s.
47
Cap´ı ulo 10 - Complejidad de algunas p opiedades 48
Hay que ene en cuen a que pa a que es o sea ealmen e un compo amien o
polin´omico, N iene que habe sido ecibido como inpu en base una ia, es deci , el
inpu Nse ep esen a ecibiendo N okens del mismo ipo. No emos que es impo -
an e po que si nos die an Ncomo inpu en bina io, po ejemplo, O(N) se ´ıa un
iempo exponencial en el ama˜no del inpu . Pe o es una hip´o esis azonable abaja
en base una ia en es e ipo de si uaciones po que si no, incluso el simple p oblema de
que un au ´oma a d´e Npasos a da un iempo exponencial en ejecu a se; mien as
que conside ando la base una ia, es como si nues o au ´oma a ue a consumiendo
okens con cada paso que da y el compo amien o se ´ıa polin´omico, lo cual esul a
bas an e m´as azonable.
Aho a que ´ıamos demos a la NP-comple i ud del p oblema de la N-alcanzabilidad
en es os sis emas: pa a ello, amos a educi el p oblema del 3-SAT (del cual es bien
conocida su NP-comple i ud) al de la N-alcanzabilidad de uno de es os sis emas.
Desc ibamos es a educci´on en de alle.
Teo ema 10.2. El p oblema de la alcanzabilidad ini a en sis emas de FSMs en
comunicaci´on es NP-comple o.
Demos aci´on. Supongamos que enemos como inpu una ´o mula de 3-SAT φ
con n a iables, y que emos decidi si φes o no sa is ac ible (es deci , esol e el
p oblema del 3-SAT) usando un sis ema de FSMs.
Vamos a c ea un sis ema Sde FSMs en comunicaci´on con a ias m´aquinas
(donde no odas las m´aquinas se comunica ´an con odas las es an es). Dos de ellas
se ´an F1, F2:F1 iene un ´unico es ado en el cual de uel e 0 an e cualquie inpu (y
pe manece en ese es ado); mien as que F2 iene, de nue o, un ´unico es ado (donde
siemp e pe manece) en el cual de uel e es a ez un 1 an e cualquie inpu . De
es a o ma, u o del no de e minismo de las comunicaciones de F1, F2, pod ´ıamos
gene a cualquie cadena compues a po ce os y unos, lo cual amos a u iliza con
m´as m´aquinas. Los ou pu s an o de F1como de F2i ´an ´unicamen e a la m´aquina
F3, que pos e io men e de ini emos.
q1
0/0
Figu a 10.1: Esquema g ´a ico de F1.
q2
0/1
Figu a 10.2: Esquema g ´a ico de F2.
Usa emos ambi´en un checke de ´o mulas de 3-SAT, que unciona ´a de la si-
guien e o ma: como la ´o mula φ, que es e checke ecibi ´a como inpu , iene n
a iables (que podemos supone o denadas de alg´un modo), el checke usa ´a los
np ime os inpu s que le lleguen (en es e caso de F1yF2, como e emos) pa a
asign´a selos como alo es de las a iables de φ, en ese mismo o den. Una ez le
lleguen esos p ime os ninpu s, pod ´a comp oba si esos alo es sa is acen φ, y gene-
a una espues a a i ma i a o nega i a. Es e checke se puede cons ui de mane a
sencilla como m´aquina de Tu ing. Y como imos en el apa ado 4.2, los sis emas
de FSMs en comunicaci´on con 2 FSMs son una clase Tu ing comple a, as´ı que es e
checke puede se implemen ado median e 2 FSMs en comunicaci´on, digamos F4, F5.
Adem´as, el checke puede se implemen ado sencillamen e de o ma que se ejecu e

Cap´ı ulo 10 - Complejidad de algunas p opiedades 49
en iempo lineal con espec o a los inpu s de las ´o mulas que ecibe. Y, como
imos en el apa ado 4.2, la ans o maci´on de m´aquinas de Tu ing a sis emas de
FSMs en comunicaci´on e a su icien emen e buena como pa a pode a i ma que
solo a˜nad´ıamos una can idad polin´omica de sob ecos e. Po an o, podemos a i ma
que el compo amien o del checke implemen ado con F4, F5se ´a polin´omico en el
n´ume o de li e ales de la ´o mula φque nos den como inpu .
Pa a comunica las m´aquinas F1, F2con es e checke (F4, F5), usa emos una
sencilla m´aquina F3in e media ia: ecibi ´a los ou pu s que F1yF2gene en, y los
deja ´a pasa (en un ´unico canal), ´unicamen e, hacia el checke , en el o den que le
lleguen. De es a o ma conseguimos simpli ica la o ma en que llegan los ce os y
unos gene ados po F1, F2al checke .
q3
0
0/0
1/1
Figu a 10.3: Esquema g ´a ico de F3.
Y po ´ul imo enemos una m´aquina F6que lo ´unico que hace es espe a la
espues a del checke . Cuando F4yF5hayan p ocesado su icien e in o maci´on como
pa a sabe si la ´o mula φes o no sa is ac ible, en ia ´an un mensaje (a i ma i o o
nega i o en cada caso, digamos que median e los li e ales >,⊥) a F6. La ecepci´on
de un mensaje a i ma i o ha ´a que F6 ansi e a un es ado di e en e q6
, que se ´a
el ´unico es ado de acep aci´on de S, o sea, que las ´unicas con igu aciones de Sde
acep aci´on son aquellas en las que F6es ´a en q6
( educiendo as´ı el p oblema a una
especie de alcanzabilidad ini a de F6den o del sis ema S). Y el p oblema de la
N-alcanzabilidad de Sen es e caso lo plan ea emos en es e caso, como explic´abamos
al inicio, como ¿alcanza Ssu con igu aci´on de acep aci´on en menos de Npasos de
S?
q6
0q6
>/
x/ (x6=>)
Figu a 10.4: Esquema g ´a ico de F6.
Con es o ya end ´ıamos nues o sis ema S= (F1, F2, F3, F4, F5, F6) cons uido,
de o ma que las di e en es m´aquinas se comunican ´unicamen e con las que mues a el
diag ama de la igu a 10.5. Veamos aho a po qu´e unciona ealmen e es a educci´on.
Cap´ı ulo 10 - Complejidad de algunas p opiedades 50
F1
F2
F3checke
(F4+F5)
inpu (φ)
F6
Figu a 10.5: Diag ama explica i o de las comunicaciones que se es ablecen en S.
Dada la cons ucci´on an e io , al checke le llega ´an ce os o unos en unci´on de
qu´e m´aquina ejecu e el siguien e paso de en e F1, F2. Supongamos que el checke
o mado po F4, F5 iene que ejecu a p(|φ|) pasos pa a pode decidi si la ´o mula
φ(deno amos po |φ|el ama˜no de la ´o mula φcomo inpu , y eco damos que iene
n≤ |φ| a iables) es o no sa is ac ible. Po la discusi´on an e io , pes un polinomio.
En onces, en caso de que φsea sa is ac ible, de iniendo N:= p(|φ|) + 2n+ 1 ≤
p(|φ|)+2|φ|+1, es cla o que en Npasos Spod ´a llega a su es ado de acep aci´on, es
deci , aquel en el que F6es ´a en q6
(p(|φ|) pasos se ´an del checke , nde las m´aquinas
F1, F2pa a gene a los li e ales que hacen φcie a, nde F3pa a deja pasa es os
li e ales po un mismo canal y 1 inal de la espues a que el checke en ´ıa a F6).
Y, cie amen e, el ec´ıp oco ambi´en es cie o: si la ´o mula φno es sa is ac ible,
en ninguna ejecuci´on de Sde longi ud Nel sis ema pod ´a llega a su es ado de
acep aci´on. Po an o, podemos conclui que la educci´on del p oblema de la sa is-
ac ibilidad de φ, una ´o mula cualquie de 3-SAT , ha sido educida a un p oblema
de N-alcanzabilidad en sis emas de FSMs en comunicaci´on.
Adem´as, la educci´on es polin´omica po que la cons ucci´on de Ses polin´omi-
ca espec o al ama˜no de φ(pues la cons ucci´on de cada m´aquina es en e dad
independien e de φ, as´ı que podemos conside a que la cons ucci´on de Ses O(1)
en cuan o a n´ume o de es ados, y lineal en cuan o a ama˜no de los bu e s, pues el
checke ecibe el inpu comple o y ninguna m´aquina m´as iene li e ales en su bu e
inicialmen e), y N ambi´en lo es.
De es a o ma, es amos ya en posici´on de a i ma que el p oblema de la N-
alcanzabilidad en sis emas de FSMs es en e ec o NP-comple o, como que ´ıamos
demos a .
De hecho, que el p oblema sea NP-comple o no debe ´ıa esul a nos una g an
so p esa en ealidad, pues el al ´ısimo g ado de no de e minismo que ienen los sis-
emas de FSMs en sus comunicaciones hace p ´ac icamen e imposible consegui que
pasen a la on e a de lo polin´omico. De hecho, incluso con ´unicamen e 2 m´aquinas,
como hac´ıamos en la demos aci´on an e io con F1yF2, el in e calado que puede
exis i en e sus ejecuciones hace que el n´ume o de posibles cadenas de ce os y unos
que le puedan llega a la F3an e io c ezca exponencialmen e con o me a los pasos
Cap´ı ulo 10 - Complejidad de algunas p opiedades 51
que ejecu an F1yF2.
Si dejamos que a F3le lleguen nli e ales, hab ´a 2ncadenas posibles que le
puedan llega , un c ecimien o cla amen e exponencial. Pe o esul a m´as in e esan e
comp oba que aunque limi emos la capacidad de in e calado de F1yF2, uel en a
gene a se una can idad exponencial de cadenas. Es o lo podemos comp oba impo-
niendo unas cie as condiciones de jus icia en es as comunicaciones.
Po ejemplo, si no dejamos que una m´aquina ejecu e m´as de k(≥2) pasos
seguidos, pod ´ıamos espe a que disminuye a bas an e el n´ume o de cadenas po-
sibles que se pueden gene a . Pe o esul a que sigue siendo exponencial, pues la
can idad de cadenas de longi ud nque se pod ´an gene a cumple la ecu encia
cn=cn−1+cn−2+. . . +cn−k, una de las llamadas sucesiones de Fibonacci gene ali-
zadas, que ienen ca ´ac e exponencial, con bases comp endidas en e ϕ≈1,6180 . . .
y 2 ([28], lema 3.6). Si limi amos que las 2 m´aquinas no puedan ejecu a kpasos
consecu i os, ob enemos un esul ado simila .
El caso m´as ue e en es e sen ido se ´ıa uno en el cual implemen ´a amos una
jus icia al que solo pe mi i´e amos ejecuciones in e caladas de F1yF2, de o ma
que, de alguna o ma, pudi´e amos di idi cada cadena ecibida po F3en g upos
de dos li e ales que pod ´ıan se ´unicamen e 01 o 10. Igualmen e, en es e caso cn≈
2n/2=√2n, que segui ´ıa siendo exponencial.
De es a o ma emos que, a´un limi ando a i icialmen e la capacidad de comuni-
caci´on de las dis in as m´aquinas median e di e en es ipos de jus icia, con inuamos
ob eniendo can idades no polin´omicas de posibles ejecuciones, lo cual nos indica que
pod´ıamos espe a el esul ado que hemos dado en es e cap´ı ulo.
10.1.1. En sis emas con bu e s aco ados
A modo de compa a i a podemos conside a el p oblema de la alcanzabilidad
ini a en el caso de sis emas de FSMs en comunicaci´on con bu e s aco ados, al
y como de inimos en el apa ado 5.1. En es e caso, y en el mismo esp´ı i u que
ob en´ıamos que su exp esi idad e a bas an e limi ada, pues son an exp esi os como
los au ´oma as ini os (como imos en 7.1), amos a consegui e que el p oblema
de la N-alcanzabilidad es mucho m´as sencillo de esol e , pues es polin´omico en N.
Lema 10.3. El p oblema de la alcanzabilidad ini a en sis emas de FSMs en comu-
nicaci´on con bu e s aco ados es polin´omico (P).
Demos aci´on. Dado un sis ema Sde FSMs en comunicaci´on con bu e s aco a-
dos, podemos consegui un au ´oma a ini o Fequi alen e, cuyo ama˜no no depende
de Ny es polin´omico en el ama˜no de S, como imos al inal del cap´ı ulo 7. Y la
cons ucci´on del g a o de alcanzabilidad de Fhas a llega a p o undidad N(pues
m´as all´a no amos a ob ene espues as al p oblema de la N-alcanzabilidad, as´ı que
no lo necesi amos) es O(N): en e ec o, a cualquie p o undidad d,Fsolo pod ´a
es a en una can idad O(1) de es ados, pues son los que esul an de conside a los
es ados de F(cons an es espec o a Npo la discusi´on an e io ); y pa a cons ui el
siguien e ni el del g a o (p o undidad d+ 1) necesi amos solo conside a los es ados
Cap´ı ulo 10 - Complejidad de algunas p opiedades 52
del ni el d. Po an o, cada ni el se c ea en iempo cons an e, y de ah´ı esul a que
llega has a el ni el Nes O(N).
Al se la educci´on del p oblema del p oblema de la N-alcanzabilidad en Sal
de la N-alcanzabilidad en Fpolin´omica en el ama˜no de S, y se ambi´en g a o de
alcanzabilidad de Fde ama˜no polin´omico en N, es cla o que el p oblema de la
N-alcanzabilidad se puede esol e en iempo polin´omico espec o al ama˜no de los
da os del p oblema.
Como emos, es o es ablece de nue o una g an di e encia en e la complejidad
de los sis emas de FSMs en comunicaci´on gene ales y los que ienen la limi aci´on de
ene los bu e s aco ados.
10.2. El p oblema de eg eso al es ado inicial
Analizamos aho a o o p oblema de decisi´on in e esan e en el caso de los sis emas
de m´aquinas de es ados o, en gene al, de dis in os ipos de au ´oma as: el p oblema
de sabe si desde cualquie con igu aci´on alcanzable se puede eg esa a la con igu-
aci´on inicial. De nue o, es e p oblema esul a en su e si´on gene al indecidible pa a
nues os sis emas u o del Teo ema de Rice, pe o podemos c ea e siones ini is-
as que sean decidibles e in e esan es al mismo iempo. En es e caso la p egun a
se ´a: pa a cualquie secuencia de Mpasos de nues o sis ema, ¿exis e un camino de
longi ud k, con k≤N, de o ma que as esos M+kpasos el sis ema uel a a su
con igu aci´on inicial? Conside a emos MyNp e ijados, como da os del p oblema.
Es e p oblema se puede exp esa de o ma l´ogica como (a modo de pseudoc´odigo):
∀paso1, paso2, . . . , pasoM∃paso0
1, paso0
2, . . . , paso0
k
es igual(inicial, aplica (inicial, [paso1, . . . , pasoM, paso0
1, . . . , paso0
k]))
Como podemos aplica acciones sob e nues os sis emas en iempo polin´omico y
la can idad de pasos es ambi´en polin´omica en MyN, es cla o que es e p oblema
es del ipo ∀P∃PP, es deci , que pe enece a la clase de complejidad ΠP
2.
Lo in e esan e a a se comp oba que de hecho es e p oblema es comple o den-
o de es a clase, lo cual nos da la idea de que es en ealidad di ´ıcil de esol e . Pa a
ello, amos a educi un p oblema del ipo del de SAT a nues o p oblema. En con-
c e o, se ´a el p oblema QSAT2( ambi´en llamado QBF2), que a a de de e mina si
una ´o mula de SAT con cie os cuan i icado es sob e a iables (en es e caso p ime-
o cie os cuan i icado es uni e sales y despu´es o os exis enciales, necesa iamen e
en ese o den) es sa is ac ible. Y es bien sabido que es e p oblema es Πp
2-comple o
(al igual que sus an´alogos QSATken Πp
k), pues de hecho son los p oblemas m´as
p o o ´ıpicos con es a p opiedad.
La idea pa a la simulaci´on de es e p oblema es cons ui un sis ema de FSMs
en comunicaci´on que simule exac amen e lo que espe amos en el p oblema QSAT2:
hab ´a una p ime a ase en la que asigna emos cualquie alo a cie as a iables de
nues a ´o mula (y pa a consegui po encialmen e cualquie asignaci´on, usa emos el
Cap´ı ulo 10 - Complejidad de algunas p opiedades 59
p esen a un esul ado que no se deduce di ec amen e de las p opiedades de o o
ipo de m´aquinas, y puede esul a in e esan e.
Con lo discu ido en los an e io es p´a a os, esul a azonable de ini el p oblema
de la aco aci´on ini a de la siguien e o ma: dado un n´ume o na u al ky una con i-
gu aci´on inicial de un sis ema de FSMs en comunicaci´on, ¿hay alguna con igu aci´on
alcanzable en la cual alguno de los bu e s enga al menos kli e ales?
P oposici´on 10.5. El p oblema de la aco aci´on ini a pa a sis emas de FSMs en
comunicaci´on es PSPACE-comple o.
Demos aci´on. Es sencillo comp oba que el p oblema es PSPACE: si el sis ema
iene nm´aquinas y kes la cons an e de aco aci´on del inpu (que, como an e io -
men e, suponemos que iene dada en base una ia), como el sis ema de FSMs no a
a ene nunca m´as de nk li e ales (en caso de que se cumpla el p oblema), se ´a sen-
cillo simula lo con nk posiciones en la memo ia de una m´aquina de Tu ing. Adem´as,
codi icando los bu e s de cada FSM en una cin a di e en e de la m´aquina de Tu ing,
es ´acil da se cuen a de que podemos simula el sis ema con una m´aquina de Tu-
ing de ama˜no polin´omico espec o al ama˜no de nues o sis ema de FSMs (donde
es e ama˜no iene ep esen ado po el n´ume o de es ados que ienen las dis in as
m´aquinas). Como podemos e , es a cons ucci´on usa una can idad polin´omica de
espacio espec o al ama˜no del inpu y simula pe ec amen e el sis ema de FSMs si
sus bu e s es ´an aco ados; as´ı que el p oblema es en e ec o PSP ACE.
Y que sea PSPACE-du o lo podemos deduci del esul ado que hemos comen-
ado an es sob e la acep aci´on en LBAs. Po an o, amos a hace una educci´on de
es e p oblema sob e acep aci´on en LBAs a nues o p oblema de sis emas de FSMs
en comunicaci´on, que sea adem´as polin´omica.
Pa a cada LBA Fy palab a ω, podemos cons ui un sis ema Sde FSMs en
comunicaci´on que lo simule, que end ´a kli e ales al inicio de su ejecuci´on en e
odos los bu e s. En conc e o, lo ha emos de o ma que los ou pu s no p oli e en.
Es o nos asegu a que podemos consegui simula odo el p oceso de acep aci´on (o no
acep aci´on) de ωsin que en Saumen e el n´ume o de li e ales en e odos los bu e s
(p opiedad de los sis emas donde los ou pu s no p oli e an). A˜nadimos al inal una
modi icaci´on a Spa a esol e el p oblema: en caso de que Facep e ω,Sllega ´a a
una de sus con igu aciones de acep aci´on. Y de cada una de es as con igu aciones de
acep aci´on de Ssimplemen e enemos que a˜nadi alg´un es ado que en e en bucle a
p oduci li e ales sin pa a .
De es a o ma Sse ´a un sis ema donde los ou pu s pueden p oli e a , y donde de
hecho, solo hab ´a alg´un bu e que enga al menos k+1 li e ales en el caso de que se
haya llegado a es os es ados en los cuales se p oducen li e ales descon oladamen e,
lo cual solo puede ocu i si Facep a ω. De es a o ma deducimos que Sno es k+ 1
aco ado si y solo si Facep a ω, y la ans o maci´on ha sido polin´omica en el ama˜no
de Fyω. Al se el p oblema de si Facep a ω PSPACE-comple o, ambi´en lo ha
de se el de la aco aci´on ini a de sis emas de FSMs.
Con es o hemos comp obado que en sis emas de FSMs en comunicaci´on, dada
su g an exp esi idad, hay p oblemas de g an a iedad de complejidades, y enemos

Cap´ı ulo 10 - Complejidad de algunas p opiedades 60
ambi´en una idea de cu´al es es a complejidad pa a algunos de los p oblemas m´as
in e esan es de los modelos concu en es que se aplican a nues os sis emas. Es e es
po an o un buen pun o de pa ida al in en a usa es e ipo de sis emas.
Cap´ı ulo 11
Un sis ema Tu ing uni e sal
En la eo ´ıa de compu abilidad ha sido siemp e un p oblema in e esan e con-
segui m´aquinas de Tu ing uni e sales lo m´as peque˜nas o sencillas posible. Se han
llegado a cons ui m´aquinas muy peque˜nas: ya en 1962 M. Minsky encon ´o una con
´unicamen e 7 es ados y un al abe o de 4 s´ımbolos, y es o ha ido mejo ´andose has a
llega , po ejemplo, a una m´aquina con solo 2 es ados (aunque 18 s´ımbolos en el
al abe o) u o a con 3 es ados y 9 li e ales en su al abe o (ambas p opues as po Y.
Rogozhin en 1996 [24]). Relajando la noci´on de Tu ing comple i ud a m´aquinas de
Tu ing que usan una cin a inicial un an o modi icada, que no enga a ambos lados
in ini os s´ımbolos de blanco (como amos a e en la eo ´ıa que desa olla emos en
las siguien es p´aginas), se han llegado a consegui m´aquinas de Tu ing uni e sales
con solo 2 es ados y 4 s´ımbolos en el al abe o (po T. Nea y y D. Woods en 2007
[22]); esul ados que ya son bas an e di ´ıciles de supe a , e incluso pod ´ıa se que en
algunos casos ue an ´op imos.
En nues o caso, amos a cons ui un sis ema de FSMs en comunicaci´on con 36
es ados en o al que sea uni e sal, y que enga un al abe o con solo 3 li e ales. No
supone ni mucho menos un n´ume o an bajo como los ´eco ds que comen ´abamos
an es, pe o supone un esul ado in e esan e en ´e minos de simplicidad: esencial-
men e el uncionamien o del sis ema es ´a concen ado en ´unicamen e 4 es ados, y
la mayo ´ıa del es o es a ´an casi epe idos, pues end ´an una es uc u a muy bien
de inida que amos a i e a . Conside amos po an o in e esan e es e esul ado po -
que esul a mucho m´as in ui i o de en ende que muchas o as de las m´aquinas que
en su momen o cons i uye on un ´eco d, que son m´as a i iciales en cuan o a sus
m´e odos de cons ucci´on y se en iende, po an o, peo la o ma en que uncionan.
La cons ucci´on que ha emos es ´a basada en el au ´oma a 110, un au ´oma a celu-
la cuyo compo amien o apa en emen e sencillo con as a con la p opiedad b´asica
po la cual es conocido: es Tu ing comple o.
Reco demos que los au ´oma as celula es son aquellos que ienen una se ie de
posiciones (no malmen e con o mas egula es, como en o ma de cuad ´ıcula o ali-
neados), pudiendo es a cada posici´on en una can idad ini a de es ados en cada
ins an e. Y es os au ´oma as an e olucionando con el iempo de o ma que el es-
ado de cada posici´on en el iempo + 1 depende ´unicamen e de del es ado de sus
posiciones ecinas en el ins an e (siendo es a elaci´on de ecindad y la o ma de
cambia de cada posici´on di e en e en cada au ´oma a).
En es e sen ido, el au ´oma a 110 simplemen e ope a en pa alelo sob e un ec o
in ini o de celdas (que podemos e como la cin a de una m´aquina de Tu ing), de
61
Cap´ı ulo 11 - Un sis ema Tu ing uni e sal 62
o ma que en cada mo imien o gene a una nue a cin a comple a, en la cual cada
posici´on depende ´unicamen e de su alo en la cin a en el ins an e an e io y la
de sus dos posiciones inmedia amen e adyacen es. El al abe o de cin a se supone
bina io (aqu´ı abaja emos con 0 y 1). Las ansiciones se pueden e en la siguien e
abla, que mues a cu´al es el alo de una celda en el ins an e + 1 sabiendo el alo
que en´ıan sus 3 celdas ecinas en el ins an e (la de su izquie da, ella misma y la
de su de echa, en ese o den):
Cin a en 111 110 101 100 011 010 001 000
Cin a en +101101110
Si in e p e amos es as ansiciones como un n´ume o en decimal, esul a se el
110 (de un o al de 256 au ´oma as di e en es que pod ´ıan de ini se del mismo modo),
de ah´ı el nomb e del au ´oma a.
Pa a simula el compo amien o del au ´oma a 110, usa emos un en oque simila
al del apa ado 6.2, en el cual nues o sis ema ba ´ıa de izquie da a de echa la cin a
de la m´aquina de Tu ing, gene ando as´ı una nue a cin a as cada ba ido. En es e
caso se aplica ambi´en la idea de e asa los ou pu s un ciclo espec o a los inpu s:
an es e a po que el cabezal pod´ıa mo e se a la izquie da, y aho a es debido a que
cada le a puede a ec a a la que es ´a a su izquie da cuando el au ´oma a gene e un
ou pu pa a la siguien e posici´on de la cin a. Vis o de o o modo, a la ho a de i
eco iendo de izquie da a de echa la cin a, hemos de eco da los dos alo es que
acabamos de e , y solo a la ho a de e el e ce o oma emos la decisi´on de saca un
ou pu , que es a ´a un ciclo e asado con o me a la idea que p opone el au ´oma a
110 (pod ´ıamos deci que el nue o alo de una celda se gene a cuando isi amos el
alo an iguo de su ecina de echa), si bien no supone un p oblema.
A modo de ejemplo enemos la igu a 11.1: si a
i ep esen a el con enido de la
posici´on ide la cin a en el ins an e , en onces las lechas diagonales lisas indican
cu´ando se gene a cada li e al de la cin a de = 1, mien as que las lechas discon i-
nuas nos indican qu´e o as posiciones hemos enido que ene en cuen a pa a gene a
dicha posici´on, y que po lo an o, de alguna mane a nues o sis ema ha de eco da .
a0
0a0
1a0
2a0
3a0
4
a1
0a1
1a1
2a1
3a1
4
Figu a 11.1: Rep esen aci´on g ´a ica de c´omo se e asan las p oducciones.
Resul a necesa io pensa ambi´en en una o ma de delimi a la cin a ac ual, pues
no que emos que el inal de la cin a en el ins an e in luya en los ou pu s gene ados
Cap´ı ulo 11 - Un sis ema Tu ing uni e sal 63
al inicio de la cin a del ins an e + 1. Pa a ello in oduci emos el li e al #, como ya
hicimos an e io men e, que deno a ´a el in de una cin a y, a la ez, el comienzo de
la siguien e.
Con es as ideas, pod ´ıamos c ea un au ´oma a bas an e sencillo que simule el
uncionamien o del au ´oma a 110, como ep esen amos en la siguien e igu a:
#
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
#/#
#/#
#/#
#/#
#/#
#/#
#/#
Figu a 11.2: Implemen aci´on de la FSM que simula las p oducciones del au ´oma a
110.
Como emos, esencialmen e es os 7 es ados ya aglu inan el uncionamien o del
au ´oma a 110, y po an o simulan algo que iene an a exp esi idad como pa a se
Tu ing comple o. Adem´as, los 4 es ados 00, 01, 10, 11 son los que lle an la mayo
pa e del signi icado, pues los o os 3 solo e lejan una especie de es ado ansi o io
del sis ema, en el cual oda ´ıa no hemos le´ıdo su icien es ca ac e es como pa a
gene a un ou pu .
Pe o aho a se nos p esen a la mayo di icul ad de la cons ucci´on: la demos a-
ci´on de que el au ´oma a 110 es Tu ing comple o, lle ada a cabo po Ma hew Cook
en 2004 [8,9] pa a da una con es aci´on posi i a a la conje u a de S ephen Wol am
en 1985, p esupone que la cin a es un poco di e en e a lo que es amos acos umb a-
dos: no es ´a ellena en e a de ca ac e es blancos a izquie da y de echa de la zona
que es amos a ando, sino que supone que hay un pa ´on epe i i o que se epi e
inde inidamen e hacia izquie da y de echa. Cook llama a es e pa ´on epe i i o ´e e ,
y es la cadena 00010011011111, de longi ud 14. Al aplica la egla del au ´oma a
110 sob e el ´e e , es e se desplaza 4 posiciones a la izquie da. De es e modo, as
7 i e aciones, ob enemos de nue o el ´e e en su posici´on inicial, y odo se epi e
c´ıclicamen e.
Cap´ı ulo 11 - Un sis ema Tu ing uni e sal 64
000100110111110001
001101111100011000
··· ···
··· ···
Figu a 11.3: Una i e aci´on de la e oluci´on del ´e e .
Lo que nos al a en onces pa a consegui que nues o sis ema simule ealmen e
el au ´oma a 110 de o ma que consigamos un sis ema Tu ing uni e sal es, de alguna
o ma, simula el ´e e . Pa a ello in oduci emos dos m´aquinas adicionales: una si-
mula ´a la c eaci´on de ´e e a la de echa de la zona de la cin a que es amos a ando
(F2), y o a a la izquie da (F0). La m´aquina que simulaba el au ´oma a 110 y que
hemos explicado en la igu a an e io se ´a la m´aquina F1. Tend emos po an o un
sis ema Scon 3 m´aquinas que se comunica ´an de mane a c´ıclica: F0le manda ´a la
cin a comple a a F1,F1aF2la nue a cin a gene ada, F2aF0la cin a habiendo
a˜nadido un ca ´ac e po la de echa, y cuando le llegue de nue o a F1a a ´es de F0,
es a hab ´a a˜nadido un ca ´ac e m´as del ´e e po la izquie da. Como comen amos,
as cada ba ido de la cin a, an o F0como F2a˜nadi ´an un ca ´ac e nue o a la
cadena que es ´a p ocesando el sis ema S. Es o hace que cada ez haya m´as li e ales
en Sy que no odos sean especialmen e ele an es (pues la mayo ´ıa an a con inua
siguiendo el pa ´on del ´e e , po que las modi icaciones no se han ex endido an o).
Sin emba go, es una mane a ´acil de esol e la cues i´on de la simulaci´on del ´e e ,
po que si no, end ´ıamos que c ea un m´e odo de de ecci´on de qu´e zonas de la cin a
han cambiado o no en cada momen o, lo cual esul a ´ıa mucho m´as cos oso.
Sin m´as dilaci´on, pasamos a de ini F0. Como o zosamen e el sis ema iene que
eco da en cu´al de los 14 elemen os del pe iodo del ´e e es ´a (po la izquie da en es e
caso), F0 iene que ene al menos 14 es ados. Veamos que bas a con 14: de inimos
un es ado qi(pa a cada i∈ {0,...,13}) de o ma que si F0es ´a en el es ado qi, es o
signi ica que el siguien e li e al a la izquie da de la egi´on de la cin a que la m´aquina
F1ha conside ado has a aho a es el i-´esimo del pa ´on del ´e e , que eco demos que
es 00010011011111. Como sabemos que, as una pasada de las m´aquinas, el ´e e se
desplaza 4 posiciones a la izquie da. Eso nos quie e deci que, si en el iempo en
una posici´on de la cin a es ´abamos en el ca ´ac e idel ´e e , en el ins an e +1 en esa
posici´on es a ´a el ca ´ac e i+ 4 (m´odulo 14, cla o). Pe o como ese ca ´ac e lo hab ´a
in oducido F0en el sis ema en iempo , y aho a es amos in e esados en el ca ´ac e
jus o a su izquie da, es deci , en el i+ 3 del ´e e . Po an o, de qi ansi a emos a
q(i+3) m´od 14. Con es o se nos c ea una es uc u a muy egula y sencilla que nos
pe mi e gene a ´e e paso a paso a la izquie da de la zona que es ´a a ando nues o
sis ema has a el momen o.
Una ez enemos es o cla o, solo enemos que da nos cuen a de cu´al es el uncio-
namien o que espe amos de F0: debe ´ıa een ia odo lo que lee, y ´unicamen e a˜nadi
una le a en la siguien e cin a, es deci , que solo a˜nade la le a co espondien e del
´e e cuando le llega el ca ´ac e # (lo cual hacemos, po simplicidad, gene ando 2
ou pu s al consumi el inpu #, lo cual imos ya as la de inici´on 5.1 que e a una

Cap´ı ulo 11 - Un sis ema Tu ing uni e sal 65
o ma azonable de in e p e a el en´omeno subyacen e de p oli e aci´on de los ou -
pu s). Todo es e pensamien o queda ´ıa plasmado en un au ´oma a de la o ma que
mos amos en la igu a 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
Figu a 11.4: Implemen aci´on de F0en la cons ucci´on.
Una ez en endida la cons ucci´on del au ´oma a F0, la cons ucci´on de F2 esul-
a sencilla po analog´ıa. Las ansiciones cambia ´an poco, pues desde el es ado qi
ansi a emos al q(i+5) m´od 14 po que es amos in e esados en la posici´on a la de echa
de la i+ 4, no en la izquie da como en F0. Y de nue o, F2solo a˜nade li e ales al
sis ema una ez sabe que le ha llegado el in de la cin a, es deci , cuando lee #. Es o
nos da ´ıa el au ´oma a de la igu a 11.5.
Cap´ı ulo 11 - Un sis ema Tu ing uni e sal 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#
Figu a 11.5: Implemen aci´on de F2en la cons ucci´on.
Po ´ul imo, comen amos c´omo se inicia odo el p ocedimien o de simulaci´on:
en F1el es ado inicial es #; en F0es q0; y en F2es q0
8(que hemos sepa ado de
q8pa a que al inicio solo se p oduzca la # que necesi amos). Adem´as, el inpu se
pond ´a en el bu e del que lee F2. As´ı, hab ´a una p ime a uel a en la cual F2
a˜nade # y F0yF2la een ´ıan. Po an o, el bu e de F2aho a end ´a el inpu
inicial seguido de #. Y con eso ya empieza el econocimien o usual, y F2empieza a
a˜nadi ca ac e es co ec amen e po que es ´a en q13 (y el ´e e a hacia la izquie da),
yF0es aba a˜nadiendo pa es co ec as del ´e e desde el p incipio.
Cap´ı ulo 12
Conclusiones
A la is a de odo el abajo expues o has a aho a, ya podemos ex ae a ias
conclusiones in e esan es sob e los sis emas de m´aquinas de es ados ini os en co-
munciaci´on. Lo p ime o que hemos comp obado es que den o del mismo ma co
e´o ico ienen cabida di e en es de iniciones, y cada una de ellas implica di e en-
es p opiedades de los sis emas. En conc e o, las e siones m´as usuales ienen una
exp esi idad bas an e al a y es ´an siemp e en la l´ınea en e lo decidible y lo indeci-
dible (como hemos is o en los cap´ı ulos 4,6,8y9). El hecho de que es ´en en es a
on e a mo i a la a iedad de de iniciones que enemos: dependiendo del caso es-
a emos in e esados en una ganancia en exp esi idad o en comp ensi´on de nues os
sis emas, y elegi emos e siones en uno u o o lado de la on e a dependiendo de
es os in e eses.
En conc e o, sabemos que los sis emas de m´aquinas de es ados gene ales son Tu-
ing comple os (cap´ı ulo 4) y eso hace que los p oblemas de decisi´on asociados a ellos
sean indecidibles (Teo ema de Rice). Pe o adem´as, e siones simpli icadas de es os
p oblemas de decisi´on (que hemos es udiado en el cap´ı ulo 10) son ambi´en di ´ıciles
de esol e en gene al, como el caso de la alcanzabilidad ini a, que hemos comp o-
bado que es NP-comple o. Adem´as, po se Tu ing comple o, podemos cons ui
sis emas que sean uni e sales. En es e caso ha sido in e esan e la cons ucci´on ba-
sada en el au ´oma a 110 (cap´ı ulo 11) po se simple y sencilla de en ende , adem´as
de ela i amen e peque˜na.
Respec o a las di e en es modi icaciones podemos deci ambi´en a ias cosas.
Sabemos que los sis emas donde los ou pu s no p oli e an son comple os den o de
los econocedo es de lenguajes dependien es del con ex o, lo que los si ´ua ce ca de la
Tu ing comple i ud, pe o hace que sean m´as sencillos de es udia a pesa de esa g an
exp esi idad. En conc e o hemos podido comp oba que algunos p oblemas de i al
impo ancia, como el de sabe si acep an un inpu dado, es decidible, aunque iene
una complejidad muy ele ada ( imos que e a PSPACE-comple o en el cap´ı ulo 10).
El caso de los sis emas donde los bu e s es ´an aco ados es m´as sencillo. Com-
p obamos que son equi alen es a los au ´oma as ini os en el cap´ı ulo 7y que eso
hace que p oblemas an e io men e es udiados como la alcanzabilidad ini a sean
polin´omicos (en el cap´ı ulo 10).
E a m´as in e esan e el caso de los sis emas donde los bu e s no ienen o den,
es udiados en el cap´ı ulo 8. En es e caso, di e en es adap aciones de la de inici´on
lle aban a la equi alencia con di e en es edes de Pe i: las usuales, con a cos in-
hibido es o con a cos es ablecedo es. En odos los casos esul aba in e esan e la
67
Cap´ı ulo 12 - Conclusiones 68
compa a i a en e la complejidad de cie os p oblemas b´asicos como la alcanzabili-
dad o el ecub imien o, que es ´an en la on e a de lo decidible e indecidible en es os
es ipos de edes de Pe i, como imos al inal del cap´ı ulo.
Po ´ul imo es udiamos una a iaci´on en la cual los canales de comunicaci´on
pueden alla , dando luga al o malismo (ampliamen e es udiado en la li e a u a)
de los Sis emas de Mensajes Pe didos. Hemos ecopilado algunos de las p opiedades
b´asicas de es os sis emas en el cap´ı ulo 9, como que el p oblema de la e minaci´on
es decidible (aunque de una complejidad ex emadamen e al a).
Con es o hemos es ablecido una eo ´ıa b´asica bas an e amplia sob e sis emas
o mados po m´aquinas de es ados ini os en comunicaci´on, que puede se i en mu-
chos o os abajos como e e encia de qu´e p opiedades son espe ables dependiendo
de las ca ac e ´ıs icas que engan nues os canales de comunicaci´on. Adem´as hemos
expues o una colecci´on bas an e amplia de a iaciones en la de inici´on p incipal, de
o ma que odos es os modelos se pod ´an eu iliza en casos en los que engamos
que implemen a p o ocolos en los cuales m´aquinas sencillas ienen que comunica se
pa a ealiza una a ea m´as compleja.