Come può una rete di Petri svelare il mistero della congettura di Collatz?

Il problema di Collatz è famoso per la sua semplicità ingannevole. Partendo da un numero intero, se è pari lo si divide per due, se è dispari lo si moltiplica per tre e si aggiunge uno. Ripetendo il procedimento, tutti i numeri sembrano finire su 1, ma nessuno ha ancora dimostrato che sia vero per ogni intero.

Un gruppo di ricercatori ha provato a guardare il problema da un’angolazione diversa: usando una rete di Petri. In una rete di Petri, i “luoghi” rappresentano gli interi e le “transizioni” le regole inverse del procedimento. Invece di partire da un numero e andare avanti, la rete parte da 1 e ricostruisce tutti i possibili predecessori.

Costruendo la rete fino a n = 1000, sono comparsi 1000 luoghi e 667 transizioni. Tra questi, 417 sono sorgenti (non hanno predecessori), 333 sono pozzi (non hanno successori) e 218 sono “orfani”, raggiungibili solo tramite la regola di divisione per 2. Il flusso dei token nella rete simula tutti i percorsi che potrebbero condurre a 1, mostrando una struttura ad albero.

Questo approccio permette di analizzare la congettura con gli strumenti della teoria dei sistemi discreti: ricorrenza, raggiungibilità e vivibilità diventano proprietà verificabili. Inoltre, la modellazione apre la porta a estensioni parametriche o induttive che superano il limite finito della rete.

In sintesi, la rete di Petri offre una visuale chiara e sistematica del “retro‑viaggio” verso 1, trasformando un enigma numerico in un problema di flusso di token.

Una rete di Petri è un modello grafico per sistemi concorrenti, costituito da posti (places), transizioni (transitions) e archi orientati. Nel caso della congettura di Collatz, ogni posto corrisponde a un intero n ≥ 1, mentre le transizioni rappresentano le due regole inverse: da n si può arrivare a 2·n (operazione inversa della divisione per 2) e, se n è dispari, a (n‑1)/3 (operazione inversa di 3n+1). La rete costruita è quindi l’inverso del grafo di Collatz, dove gli archi puntano verso i predecessori.

Il concetto di “marcatura” (marking) indica quanti token sono presenti in ciascun posto. Partendo da una marcatura con un token in 1, l’attivazione delle transizioni genera tutti i percorsi possibili verso numeri più grandi. La proprietà di raggiungibilità (reachability) consente di verificare se un dato intero è raggiungibile da 1, ovvero se esiste una sequenza di transizioni che lo porta a 1 nel grafo originale. La vivibilità (liveness) garantisce che, una volta inserito un token in un posto, esista sempre almeno una transizione abilitata, evitando deadlock.

L’analisi di ricorrenza (recurrence) studia se certi sotto‑insiemi di posti vengono visitati infinite volte in esecuzioni non terminate, fornendo indizi sulla possibile ciclicità di sequenze Collatz. Inoltre, la modellazione permette di introdurre parametri: ad esempio, si può definire una transizione parametrica che rappresenta n → k·n per qualunque k pari, estendendo il modello a versioni generalizzate del problema.

Dal punto di vista computazionale, la costruzione della rete fino a nmax = 1000 richiede la generazione di tutti i predecessori di ciascun nodo, con complessità O(nmax·log nmax) per la gestione delle divisioni e dei controlli di disparità. I risultati mostrano una notevole quantità di nodi “orfani”, cioè posti che hanno solo archi entranti da transizioni di tipo 2·n ma nessun arco uscente di tipo (n‑1)/3, evidenziando la asimmetria intrinseca del processo.

Infine, la formalizzazione in termini di reti di Petri apre la porta a tecniche di verifica automatica, come model checking, per dimostrare proprietà globali (ad esempio, “tutti i token raggiungono 1 in un numero finito di passi”). Questo approccio potrebbe rivelarsi un ponte tra la teoria dei sistemi discreti e la più tradizionale teoria dei numeri, offrendo nuovi strumenti per affrontare un problema rimasto irrisolto per decenni.