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[1], 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. In caso di risposta negativa la tassellatura si definisce aperiodica.[1]
Problema del domino[modifica | modifica wikitesto]
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[2] e che il problema algoritmico di determinare se un insieme di tasselli può tassellare il piano è diventato noto come problema del domino.[3]
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.[1][4][5]
Secondo Robert Berger, allievo di Wang:[3]
«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.»
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.[3]
Note[modifica | modifica wikitesto]
- ^ a b c Martin Gardner, Una straordinaria tassellatura non periodica che arricchisce la teoria delle tassellature, in Le Scienze, n. 105, maggio 1977, p. 120. Una tassellazione non periodica, in generale, potrebbe essere ricondotta ad una periodica con opportune traslazioni dei tasselli. Se ciò non fosse possibile si dice aperiodica.
- ^ Peter Renz, Mathematical proof: What it is and what it ought to be, in The Two-Year College Mathematics Journal, vol. 12, n. 2, 1981, pp. 83–103, DOI:10.2307/3027370..
- ^ a b c Robert Berger, The undecidability of the domino problem, in Memoirs of the American Mathematical Society, vol. 66, 1966, p. 72, MR 0216954. Berger conia il termine "tasselli di Wang" e dimostra per primo l'esistenza di un insieme di essi in grado di produrre una tassellatura aperiodica.
- ^ Wang Hao, Proving theorems by pattern recognition—II, in Bell System Technical Journal, vol. 40, n. 1, 1961, pp. 1–41, DOI:10.1002/j.1538-7305.1961.tb03975.x. Wang espone le sue tassellature e congettura che non abbiano insiemi aperiodici.
- ^ Wang Hao, Games, logic and computers, in Scientific American, November 1965, pp. 98–106. Viene presentato a livello divulgativo il problema del domino.
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Tasselli di Wang
