Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912755295977472 |
|---|---|
| author | Canfora, Fabrizio Cedeno, Marco |
| author_facet | Canfora, Fabrizio Cedeno, Marco |
| contents | We introduce a partial decidability protocol for the Wang tiling problem (which is the prototype of undecidable problems in combinatorics and statistical physics) by constructing a suitable mapping from tilings of finite squares of different sizes. Such mapping depends on the initial family of Wang tiles (the alphabet) with which one would like to tile the plane. This allows to define effective entropy and temperature associated to the alphabet (together with the corresponding partition function). We identify a subclass of good alphabets by observing that when the entropy and temperature of a given alphabet are well-behaved in the thermodynamical sense then such alphabet is a good candidate to tile the infinite two-dimensional plane. Our proposal is tested successfully with the known available good alphabets (which produce periodic tilings, aperiodic but self-similar tilings as well as tilings which are neither periodic nor self-similar). Our analysis shows that the Kendall Tau coefficient is able to distinguish alphabets with a good thermodynamical behavior from alphabets with bad thermodynamical behavior. The transition from good to bad behavior is related to a transition from non-chaotic to chaotic regime in discrete dynamical systems of logistic type. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13268 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping Canfora, Fabrizio Cedeno, Marco Statistical Mechanics Information Theory High Energy Physics - Theory Logic We introduce a partial decidability protocol for the Wang tiling problem (which is the prototype of undecidable problems in combinatorics and statistical physics) by constructing a suitable mapping from tilings of finite squares of different sizes. Such mapping depends on the initial family of Wang tiles (the alphabet) with which one would like to tile the plane. This allows to define effective entropy and temperature associated to the alphabet (together with the corresponding partition function). We identify a subclass of good alphabets by observing that when the entropy and temperature of a given alphabet are well-behaved in the thermodynamical sense then such alphabet is a good candidate to tile the infinite two-dimensional plane. Our proposal is tested successfully with the known available good alphabets (which produce periodic tilings, aperiodic but self-similar tilings as well as tilings which are neither periodic nor self-similar). Our analysis shows that the Kendall Tau coefficient is able to distinguish alphabets with a good thermodynamical behavior from alphabets with bad thermodynamical behavior. The transition from good to bad behavior is related to a transition from non-chaotic to chaotic regime in discrete dynamical systems of logistic type. |
| title | Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping |
| topic | Statistical Mechanics Information Theory High Energy Physics - Theory Logic |
| url | https://arxiv.org/abs/2507.13268 |