标题： 统计力学和混沌映射的王氏镶嵌问题的部分可判定协议 显示英文标题

标题： Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping

摘要： 我们通过构建不同大小有限正方形的铺砌的适当映射，引入了王铺砌问题的部分可判定协议（这是组合数学和统计物理中不可判定问题的原型）。这种映射取决于希望用以铺砌平面的初始王瓷砖族（字母表）。这使得可以定义与字母表相关的有效熵和温度（以及相应的配分函数）。我们通过观察发现，当给定字母表的熵和温度在热力学意义上表现良好时，这样的字母表可以铺砌无限二维平面。我们的提议已成功地在已知的可用良好字母表上进行了测试（这些字母表产生周期性铺砌、非周期但自相似的铺砌以及既非周期也非自相似的铺砌）。我们的分析表明，肯德尔τ系数能够区分具有良好热力学行为的字母表和具有不良热力学行为的字母表。从良好到不可判定行为的转变与逻辑斯蒂型离散动力系统中从非混沌到混沌区域的转变有关。 显示英文摘要

摘要： 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 can 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 undecidable behavior is related to a transition from non-chaotic to chaotic regime in discrete dynamical systems of logistic type.