Tasselli di Wang
# Tasselli di Wang

I tasselli di Wang (o domino di Wang), inizialmente proposti dal matematico, logico e filosofo Wang Hao nel 1961, sono una classe di sistemi formali, visualizzabili come tasselli quadrati, con un colore su ciascun lato, che possono tassellare il piano, disponendoli affiancati lungo il lato del medesimo colore, senza ruotarli o rifletterli specularmente.

Poiché all'epoca gli esperti ritenevano che non esistessero insiemi di tasselli in grado di tassellare il piano soltanto in modo non periodico, ritenendo che si potessero sempre operare traslazioni tali da ricondursi a schemi periodici, la domanda fondamentale che si pose Wang fu se un insieme dei suoi tasselli, in grado di tassellare il piano in modo non periodico, potesse farlo anche in modo periodico.

## Problema del domino

L'idea di vincolare i tasselli adiacenti a farne combaciare i colori ricorda la regola del gioco del domino, da qui il fatto che i tasselli siano noti anche come domino di Wang e che il problema algoritmico di determinare se un insieme di tasselli può tassellare il piano è diventato noto come problema del domino.

Nel 1961, Wang ipotizzò che se un insieme finito di suoi tasselli avesse potuto tassellare il piano, allora sarebbe dovuto esistere anche una tassellatura periodica con quei tasselli. A tale scopo dimostrò che se e solo se esistesse un algoritmo per decidere la tassellabilità con un insieme di domino, allora, se tale insieme tassellasse non periodicamente il piano, lo dovrebbe tassellare anche periodicamente.

Secondo Robert Berger, allievo di Wang:

«The Domino Problem deals with the class of all domino sets. It consists of deciding, for each domino set, whether or not it is solvable. We say that the Domino Problem is decidable or undecidable according to whether there exists or does not exist an algorithm which, given the specifications of an arbitrary domino set, will decide whether or not the set is solvable.»

«Il problema del domino riguarda la classe di tutti gli insiemi di domino. Consiste nel decidere, per ogni insieme di domino, se sia o meno risolvibile. Diciamo che il problema del domino è decidibile o indecidibile a seconda che esista o non esista un algoritmo che, date le specifiche di un insieme di domino arbitrario, deciderà se l'insieme è risolvibile.»

(Robert Berger)

In altre parole, il problema del domino si chiede se esista un algoritmo che decida il problema della tassellabilità per tutti gli insiemi di domino dati, ossia, dato un gruppo di tasselli come quello in figura, iniziato a tassellare il piano, si riesce ad andare avanti all'inifinito?

Nel 1966, Robert Berger risolse il problema del domino in senso negativo. Egli dimostrò che non può esistere alcun algoritmo in grado di risolverlo, mostrando come si potesse tradurre qualsiasi macchina di Turing in un insieme di tasselli di Wang che tassellino il piano se e solo se la macchina di Turing non si ferma. L'indecidibilità del problema dell'arresto (il problema di verificare se una macchina di Turing alla fine si arresta) implica quindi l'indecidibilità del problema della tassellatura di Wang.

