In questo articolo, Achille Frigeri ed Emanuele Rodaro, attraverso un racconto infestato di fantasmi, ci introducono al mondo degli automi sincronizzanti. Achille Frigeri è professore a contratto al Dipartimento di Matematica del Politecnico di Milano e si occupa della questione di decidibilità di logiche temporali, di algebra universale e di didattica della matematica. Emanuele Rodaro è professore associato al Dipartimento di Matematica del Politecnico di Milano e i suoi interessi di ricerca comprendono la teoria combinatoria di semigruppi e gruppi, la teoria algebrica e combinatoria di automi e l’interazione di queste discipline con l’informatica teorica. 

di Achille Frigeri ed Emanuele Rodaro

“Si narra che nel 1964 un giovane industriale nel settore tessile acquistò una villa in Pennsylvania, che scoprì poi essere infestata da due entità soprannaturali che soprannominò ‘Canterino’ e ‘Risino’ per via dei rumori insopportabili che emettevano in continuazione. Canterino aveva la passione per la musica swing, e spesso lo si sentiva cantare per intere ore, mentre Risino lanciava agghiaccianti e rumorose risate che davano un’atmosfera da cimitero alla villa. Col tempo il giovane industriale scoprì l’esistenza di due manufatti: un antico organo nella vecchia e polverosa soffitta e un incensiere in alabastro nell’umida cantina. Provando a suonare l’organo, strimpellando qualche nota, scoprì che a volte le entità interrompevano il frastuono. Col tempo scoprì che anche accendendo l’incensiere le entità smettevano a volte di fare rumore. Dopo diversi tentavi capì come stavano le cose. Se le due entità facevano rumore contemporaneamente, allora l’incensiere interrompeva il rumore di entrambe. Se però una sola faceva rumore, l’incensiere non aveva alcun effetto. L’organo faceva interrompere il frastuono se sia Risino sia Canterino facevano rumore, ma quando nessuno dei due faceva rumore l’organo risvegliava Canterino. Notò anche che se solo Canterino cantava, l’organo lo faceva smettere, ma faceva apparire Risino con le sue agghiaccianti risate. Infine, suonando in presenza del solo Risino, compariva anche Canterino.”

È facile convincersi che in ogni situazione, suonando l’organo e accendendo l’incensiere in un ordine ben determinato, si può far tacere entrambe le entità. Chiaramente questa sequenza di azioni dipende dalla situazione iniziale: per esempio, le azioni che il padrone di casa deve eseguire sono diverse a seconda di quante e quali entità fanno rumore in quel preciso istante. Tuttavia, ci chiediamo se esista una sequenza di azioni che permetta di interrompere il rumore prodotto da Canterino e Risino, indipendentemente dalla situazione iniziale. Il rompicapo apparve nel libro del 1965 “An Introduction to Cybernetics” di W. Ross Ashby^{[1 ]}W. Ross Ashby (1956): An Introduction to Cybernetics (Chapman & Hall, London), http://pespmc1.vub.ac.be/books/IntroCyb.pdf. e può essere descritto (e risolto) facendo uso del concetto di automa a stati finiti. Un automa è un modo compatto per descrivere come un sistema, che si può trovare in un insieme finito di situazioni, chiamate “stati”, reagisce a certi input (codificati con simboli di un certo “alfabeto”) che gli vengono forniti in modo discreto. Nel nostro caso gli stati possono essere descritti dalle seguenti quattro situazioni:

• Silenzio (S) che descrive la situazione in cui le entità non fanno rumore;
• Solo Risino fa rumore (R)
• Solo Canterino fa rumore (C)
• Sia Risino sia Canterino fanno rumore (RC)

Le azioni che fanno cambiare lo stato del sistema sono due: suonare l’organo, che possiamo abbreviare con la lettera o, oppure accendere l’incensiere, che abbreviamo con la lettera i. Se, come si usa di solito, indichiamo con Q l’insieme degli stati e con Σ l’alfabeto, avremo Q={S,R,C,RC} e Σ={o,i}. Ora possiamo rappresentare gli stati del sistema come circoletti distinti individuati con un’etichetta che riporta il nome dello stato. Le azioni sono operazioni che fanno passare da uno stato del sistema ad un altro: un espediente grafico per rappresentarle è disegnare una freccia etichettata dalla lettera corrispondente all’azione e che connetta uno stato a quello in cui evolve il sistema applicando l’azione considerata. Per esempio, dalle regole descritte nel rompicapo abbiamo che se Canterino canta, allora l’organo lo fa smettere, ma fa apparire Risino. Possiamo descrivere graficamente questa azione disegnando una freccia dallo stato C allo stato R etichettata dall’azione o, così:

Una freccia tra due stati con un’etichetta si chiama transizione. Un’altra transizione è quella che descrive la regola che per cui se una sola entità è attiva, l’incensiere non cambia la situazione. Per esempio, se Risino fa rumore, l’incensiere non lo zittisce, avremo quindi la seguente transizione:

Per ottenere una forma più compatta, rappresentiamo le transizioni in cui gli stati connessi dalla freccia coincidono (dette significativamente “autoanelli”) con uno solo stato e disegnando un “cappio”, in questo modo:

A questo punto possiamo descrivere l’intero sistema disegnando una sola volta ciascuno stato e aggiungendo tutte le frecce aventi per sorgente un qualunque stato e per etichetta una qualunque azione. Nel caso che stiamo analizzando avremo dunque quattro stati opportunamente collegati tra loro con otto frecce (cioè il numero degli stati per il numero delle azioni). Dall’analisi del problema perveniamo al seguente diagramma:

Quella che abbiamo ottenuto è la rappresentazione di un (semi)automa^{[2 ]}Un automa non è altro che un semiautoma in cui alcuni stati due stati sono scelti come “iniziali” e “finali”, immaginando dunque un sistema che evolve da una configurazione iniziale ad una finale entrambe note. che, come è chiaro, non è altro che un espediente grafico per rappresentare una funzione τ: Q x Σ → Q, detta funzione di transizione. Questo formalismo permette di calcolare in modo immediato quale sarà lo stato di arrivo se da un certo stato di partenza si applica una sequenza di azioni, ovvero semplifica il calcolo dell’iterazione della funzione τ. Per esempio, se dallo stato R si applicano in sequenza le azioni iooio, corrispondenti ad accendere l’incensiere, suonare l’organo due volte, accendere ancora l’incensiere ed infine suonare l’organo, il sistema evolverà nello stato C: osservando l’automa si vede facilmente che partendo dallo stato R e percorrendo il cammino (cioè una sequenza di frecce adiacenti) etichettato da iooio si arriva nello stato C. Matematicamente abbiamo calcolato l’immagine della funzione τ(τ(τ(τ(τ(R,i),o),o),i),o) semplicemente ispezionando l’automa ponendo il dito sullo stato R e spostandolo seguendo il percorso delle frecce. Il problema originale si può allora riformulare così: trovare una sequenza di azioni che indipendentemente dallo stato del sistema in cui è applicata, porti il sistema in un medesimo stato (possibilmente S). La sequenza (o parola) iooio non ha questa proprietà dato che se partiamo da R arriviamo nello stato C, mentre da RC ritorniamo nello stato di partenza. Una parola che risolve il problema, se esiste, viene chiamata parola di reset o parola sincronizzante. L’idea è che una tale parola possa resettare il sistema (cioè riportarlo in uno stato fissato) indipendentemente dallo stato in cui questo si trova, informazione che di solito non è accessibile, o comunque è difficile da reperire. Non tutti gli automi possiedono una parola di reset, e nel caso ne possiedano almeno una, vengono chiamati automi sincronizzanti o di reset. L’automa descritto sopra è sincronizzante e una parola di reset che risolve anche il rompicapo è data da ioooioooi. Infatti (provare per credere!), partendo da un qualunque stato e applicando la precedente parola si arriva sempre nello stato S, quello in cui le due entità sono silenziose. Questa sequenza è anche la più corta, nel senso che non esiste una parola con meno di 9 lettere che sia di reset.  È facile vedere che se una parola di reset esiste allora ce ne sono infinite altre, così che non ha senso chiedersi quale sia quella più lunga. Invece non è un problema affatto banale determinare se ne esista una e quale sia la lunghezza di quella più corta. Nel 1964 Jan Černý^{[3 ]}J. Černý, Poznámka k homogénnym eksperimentom s konecnými automatami.
Matematycko-fyzikálny Casopis Slovenskej Akadémie Vied 14 (1964) 3, 208–216. Un’ampia discussion del lavoro di Černý e degli sviluppi successivi si trova in Mikhail V. Volkov, Syncronizing Automata and the Černý Conjecture, Lecture Notes in Computer Science 5196 (2008). mostrò che per ogni naturale n è possibile costruire un automa sincronizzante (nel caso n=4 si ottiene proprio l’automa sopra) la cui più corta parola di reset ha lunghezza (n-1)². Per esempio, la parola di reset ioooioooi dell’automa sopra ha lunghezza 9=(4-1)² e, come abbiamo detto, non esistono altre parole di reset più corte. L’autore congetturò dunque che quello trovato è proprio il limite superiore, ovvero che un automa sincronizzante con n stati ha sempre una parola di reset di lunghezza al più (n-1)². Oggi sappiamo che è molto probabile che un automa generato casualmente sia sincronizzante e che mediamente la parola di reset più corta è formata da un numero di lettere proporzionale al numero degli stati, così che la congettura di Černý vale “quasi sempre”. Recentemente^{[4 ]}Abraham Gutierrez, Circulant Automata Synchronize with high probability. SandGAL 2019. si è anche dimostrato che se si genera casualmente un automa con una lettera che agisce circolarmente (come l’azione o del nostro esempio), allora con alta probabilità questo è sincronizzante e la parola di reset più corta soddisfa il limite quadratico della congettura. Tuttavia, nonostante gli intesi sforzi della comunità matematica degli ultimi 55 anni, la congettura rimane ancora aperta nella sua piena generalità.

“Si narra che sebbene il padrone della villa fosse riuscito a liberarsi delle entità malefiche, rendendo finalmente silenziose le sue notti, l’ossessione per la ricerca di una soluzione alla congettura di Černý lo abbia tormentato fino all’ultimo, come se la maledizione della villa non fosse mai svanita…”