Macchina di Turing: cos'è e cosa c'entra il quinto alacre castoro

Era il 1936 quando Alan Turing, crittografo, padre dell’informatica, uno dei più grandi matematici del XX secolo, presentò la macchina di Turing. Si tratta del modello matematico di un dispositivo di calcolo ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. È uno degli strumenti più importanti nella teoria della computazione ed è utilizzato per formalizzare il concetto di algoritmo e di “computabilità“.

Cos’è la macchina di Turing e quali sono i suoi componenti

Scendere nel dettaglio di cos’è la macchina di Turing richiederebbe una spiegazione matematico-scientifica piuttosto rigorosa. Ai nostri fini, basti pensare alla macchina di Turing come a un sistema formato da un programma in input finito: contiene le istruzioni che specificano il simbolo da scrivere sul nastro e la direzione in cui la testina deve spostarsi (verso destra o sinistra).

La macchina può assumere un insieme finito di stati mentre la funzione di transizione, dato lo stato attuale della macchina e il simbolo sul nastro, determina cosa scrivere, la direzione in cui spostare la testina e il successivo stato. Lo stato iniziale, ovviamente, è lo stato in cui si trova la macchina all’avvio delle computazione; lo stato di arresto corrisponde al singolo stato o a più stati in cui la macchina si ferma e termina l’attività di elaborazione.

L’importanza della macchina di Turing

Come accennato in precedenza, la macchina di Turing formalizza il concetto di algoritmo, fornendo un modello matematico preciso che descrive cosa significhi elaborare una funzione. La macchina può essere pensata come un calcolatore ideale, matematicamente ben definito e dal funzionamento deterministico.

In termini teorici, sia le macchine di Turing che i calcolatori moderni sono equivalenti per quanto riguarda la computabilità. Qualsiasi cosa che una macchina di Turing può calcolare, un calcolatore moderno può a sua volta calcolarla, e viceversa.

La macchina di Turing è un modello matematico astratto (anche se negli anni ne sono state realizzate diverse implementazioni fisiche). Sono quindi utili per comprendere i principi fondamentali della computazione, mentre i calcolatori di oggigiorno sono strumenti pratici progettati per eseguire calcoli reali.

La tesi di Church-Turing afferma che qualsiasi funzione calcolabile in modo intuitivo possa essere gestita con una macchina di Turing. Questo ha implicazioni profonde sulla teoria della computazione. Le macchine di Turing sono inoltre utilizzate per studiare problemi di decidibilità, ossia stabilire quali problemi possano essere risolti algoritmicamente. Inoltre, sono fondamentali nella teoria della complessità computazionale, che studia l’efficienza degli algoritmi in termini di tempo e spazio.

Cos’è l’alacre castoro

L’alacre castoro (o “busy beaver“, in inglese) è un concetto teorico nel campo dell’informatica e della teoria della computazione. Fu introdotto da Tibor Radó nel 1962 ed è utilizzato per esplorare i limiti della computazione e la complessità degli algoritmi. Il problema del busy beaver riguarda la ricerca della macchina di Turing più efficiente che, a partire da un nastro vuoto, scrive il massimo numero possibile di simboli “1” prima di fermarsi.

Si prende in considerazione una macchina di Turing che ha un insieme finito di stati, un alfabeto finito (di solito {0, 1}), una funzione di transizione che determina le azioni della macchina (scrivere un simbolo, spostarsi a sinistra o a destra sul nastro, cambiare stato), uno stato iniziale e uno di arresto (halting state).

Prendendo in esame la problematica da un punto di vista matematico, la funzione BB(n) rappresenta il massimo numero di simboli “1” che una macchina di Turing con n stati può scrivere sul nastro prima di arrestarsi. Anche per valori relativamente piccoli di n, il valore di BB(n) può essere incredibilmente grande.

Non esiste un algoritmo generale che possa calcolare BB(n) per ogni n. Lo ha dimostrato anche lo stesso Turing, spiegando che un algoritmo non può decidere se la macchina si fermi oppure no (si chiama problema della fermata). La velocità con cui BB(n) cresce è più veloce di qualsiasi funzione calcolabile (qualsiasi funzione che possa essere calcolata da una macchina di Turing).

Cosa sono le regole o gli stati di una macchina di Turing e perché il valore di BB(n) aumenta velocemente

Le regole o stati di una macchina di Turing sono le “condizioni” in cui la macchina può trovarsi. Possono essere pensati come le diverse modalità operative.

Ogni singola regola definisce quanto segue:

a) Lo stato attuale
b) Il simbolo letto sul nastro
c) Il simbolo da scrivere
d) La direzione in cui muoversi (destra o sinistra)
e) Il nuovo stato in cui passare

Esempio semplificato: “Se sei nello stato A e leggi 0, scrivi 1, muovi a destra, e passa allo stato B“.

Il valore di BB(n) aumenta in modo esplosivo perché con n regole i comportamenti della macchina tendono a divenire molto più complessi. Piccole modifiche nelle regole possono portare a comportamenti radicalmente diversi. Così, alcune macchine possono entrare in cicli molto lunghi prima di fermarsi o addirittura non fermarsi mai (si pensi ai cicli infiniti, ben noti agli sviluppatori). È spesso impossibile prevedere se una macchina si fermerà senza simularla.

I valori conosciuti della funzione BB(n) e il risultato ottenuto dopo decine di anni

I valori conosciuti della funzione BB(n) sono pochi, ma molto significativi:

BB(1) = 1
BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) = 47.176.870

È interessante notare come i valori crescano enormemente all’aumentare di n. Il “ritmo di crescita” mette bene in evidenza la complessità che può scaturire da regole semplici.

L’ultimo valore, relativo a BB(5), era noto già da anni ma non era mai stato formalmente dimostrato. Come spiega Ben Brubaker, Dopo decenni di incertezza, un team di ricerca ha finalmente determinato con precisione quanto complesso possa diventare un semplice programma per computer. La ricerca del cosiddetto “quinto busy beaver” (BB(5)) rappresenta una pietra miliare nella teoria della computazione, gettando nuova luce sui limiti di ciò che i computer possono calcolare.

Il quinto alacre castoro: un team di studiosi ne accerta il valore

Nel 1989, Heiner Marxen e Jürgen Buntrock scoprirono che una macchina a 5 stati si fermava dopo 47.176.870 passi. Per decenni, questo è rimasto il record, ma nessuno era riuscito a dimostrare che quel valore fosse effettivamente il quinto busy beaver.

La difficoltà risiede nel fatto che per provare che un certo numero sia effettivamente BB(5), bisogna dimostrare che tutte le altre macchine con 5 regole o si fermano prima o non si fermano mai. Quest’ultimo caso è particolarmente insidioso, poiché si ricollega al famoso “problema della fermata” di Alan Turing, che dimostrò essere “indecidibile” in linea generale.

Nel 2022, il ricercatore e scrittore scientifico Tristan Stérin ha lanciato il “Busy Beaver Challenge“, un progetto collaborativo online. Il team, composto da oltre 20 collaboratori in tutto il mondo, ha sviluppato nuove tecniche e strumenti software per analizzare il comportamento delle macchine di Turing. Un contributo chiave è arrivato dalla sviluppatrice Maja Kądziołka che ha utilizzato il software di verifica formale Coq per certificare la correttezza delle dimostrazioni. Questo ha permesso di raggiungere un livello di rigore senza precedenti.

Dopo mesi di intenso lavoro, il team di studiosi ha completato la dimostrazione formale che evidenzia come BB(5) sia proprio uguale a 47.176.870. Il risultato rappresenta un trionfo della collaborazione scientifica e dell’ingegnosità umana, unendo competenze diverse e sfruttando le moderne tecnologie di verifica.

L’importanza di questo risultato va oltre il mero valore numerico. Ci offre nuove prospettive sui limiti della computazione, mostrando quanto possano diventare complessi anche programmi apparentemente semplici. Le tecniche sviluppate per la ricerca di BB(5) potrebbero avere applicazioni in altri campi dell’informatica teorica e della verifica formale di programmi.

La ricerca dei busy beaver potrebbe aver raggiunto oggi un punto di svolta. Recenti scoperte suggeriscono che determinare BB(6), quindi il sesto alacre castoro, potrebbe essere equivalente a risolvere la nota “congettura di Collatz“, un problema matematico aperto ormai da decenni. Ciò implica che BB(5) potrebbe essere l’ultimo busy beaver calcolato in forma esatta.

L’immagine in apertura è tratta dal video di Mike Davey, pubblicato su YouTube.