Firing Squad Problem

Imagineu que som en una època convulsa, o en un país no massa democràtic. Assitim en una execució per afusellament. Tenim el pelotón de afusilamiento preparat, tots un al costat de l'altre, encarats a la víctima (o amb sort serà un entrenament i apuntaran a un sac de patates). El primer de tots (el cap de l'esquadró) és el que controla l'operació, i dóna la ordre: shoot when ready! (disparin quan estiguin llestos).

El normal seria que digués "fire!" i que tots disparessin a la vegada. Però assistim a un equip bastant peculiar. En el nostre cas, cada soldat només pot parlar amb el que té al seu costat, tant per l'esquerra com per la dreta (amb l'excepció del cap, que no tindrà ningú a l'esquerra; i el soldat de l'altra banda, que no tindrà ningú a la dreta). Per tant, el cap donarà l'ordre, i cal que al cap d'un cert temps, tots i cada un dels soldats disparin a la vegada, per primer i únic cop.

Com us ho faríeu? Quin protocol de comunicació seguiríeu de tal manera que l'ordre s'extengués i tots l'executessin a la vegada? Recordeu que només disposem de la informació que els nostres veïns ens puguin proporcionar...

No mola, però tot sigui per la ciència

Encara res? Imagino que no. No és una cosa trivial... El problema el va plantejar un tal J. Myhill l'any 1957. Es va publicar per primer cop el 1962, i el 1966 Abraham Waksman, va proposar An Optimum Solution to the Firing Squad Synchronization Problem.

És un problema més aviat computacional. De fet, correspon a un problema resoluble mitjançant autòmates, que no són més que màquines abstractes. L'abstracció d'un ordinador, podria dir-se. Perquè sí, abans no existien els ordinadors com els coneixem ara, i els matemàtics sempre han realitzat models abstractes de tot.

Aquest cas concret correspon als cellular automata. Aquesta màquina està formada per una tira de cel·les, col·locada una al costat de l'altra (en el cas que sigui només a lo llarg). El temps transcorre per torns, i en cada torn cada cel·la està en un estat determinat. L'estat en el que estarà cadascuna en el torn següent dependrà del meu estat i/o de l'estat dels meus veïns.

Representació imaginària d'un cellular automata. Ojo, que pot tenir més estats que 0 i 1.

Per tant, cada cel·la és un soldat, i estan en fila. Cada soldat està en un estat, incloent, però no limitat a: "no fer res", "se me hace tarde", "mira lo que me ha dicho el de al lado", i "foc!". El que pensi i faci el soldat en cada torn depèn del que ell pensi, i del que li hagin dit els veïns en el torn anterior.

En l'instant inicial el cap de l'esquadró dóna la ordre, i aquesta es va propagant per l'equip. El que va fer el senyor Waksman, és donar el conjunt de canvis d'estat necessaris per fer que totes les cel·les arribin a la vegada a l'estat de "foc!". És a dir, va determinar què han de pensar i dir exactament els soldats segons el que li arriba pels seus veïns.

I sí... funciona. Va definir 16 estats diferents i va donar les taules de transició entre estats. La solució és vàlida per un pelotón de amb un número de soldats tan gran com es vulgui. L'única pega és que es tardarà "2n-2" torns en realitzar l'execució (on "n" és el nombre de soldats).

Solucions amb menys estats, més ràpides, més lentes, etc... s'han anat presentant al llarg del temps. És important, però, que el número d'estats no depengui mai del nombre de membres, per fer la solució sostenible encara que el nombre de membres creixi.

I òbviament, el problema s'ha anat generalitzant a mesura que s'ha anat resolent. Per exemple:
- El jefe pot estar en qualsevol posició dintre del pelotón.
- El pelotón pot ser rectangular (sí, ja sé que no té sentit) de MxN soldats. Reformuleu el problema si no, com a un fotimè d'estudiants graduats amb birret en una sala d'actes i han de tirar el birret a l'aire tots a la vegada, podent parlar només amb els veïns.

Evolució d'un cas en dues dimensions i el jefe per entremig. Mireu com al final tots acaben a la vegada.

--------------------------------------------------------------------------
Què collons m'explica aquest? No havia anat a fer nano-nosequè? I coses biològiques?

Doncs sí, però la idea és modelar les nanomàquines com a diminuts autòmates que puguin funcionar amb un mínim programa. I sabem que les comunicacions entre ells no seràn fàcils, pel medi i mitjans de que es disposen... per tant, trobar una manera com aquesta, de coordinar una acció de moltes entitats, només comunicant les entitats més properes, sembla una bona idea.

De fet, em recorda una mica el tema del Quorum Sensing de l'altre dia. Bueno, millor vaig a dormir, que desvariejo. Bona nit.