『天问：世界观的对话』https://t.cn/A6GtwIRc 我和同门学妹韩雅俐也算神交，我读书时，听导师提过准备考学的一个学生不错，说的就是她。然后我毕业，她考上了。毕业后的几年，互加微信，她业余在做公众号【虾米犟】，而我，也做公众号，我俩都是出于个人爱好去认真写认真观察世界，虽从未谋面，却在偶尔线上联系时并不陌生，因为总会互读对方的文字，如见其面。文章这种东西很奇怪，像是彼此了解的名片，无需赘言，秉性能猜个大概。这篇文章呢，是源于我俩共同关注的一个中国美院发起的论坛项目，我们没有参与，但是主办方及策划小组提出的28个问题，看似学术，涉及人文科学方方面面，但实际命题适用于每个热爱生命，敬畏人性，对世界充满好奇心的人去共同思考。于是，雅俐就以个人名义私下借这些问题玩起了击鼓传花，我就是她发出传花邀请的对象之一。艺术也好，科学也罢，终归探讨的是人的问题。本周小津叨叨叨便是雅俐发我项目组问题后，我做出的浅薄回答，不甚成熟，贵在诚恳。[爱你][挤眼][鲜花]
最近身边总会有很多焦虑的声音，各种课业和生活的压力什么的，还有谈论内卷之事，以至于我现在看到卷这个字我就有点抵触，其实我本身自己就没有太在乎身边的人怎么样去卷？因为老是抱着一种做好自己就行了的态度，看着大家讨论这些，甚至到了焦虑烦躁的地步，我有些觉得自己格格不入了。
喜欢最近看的文章，其实对于内卷的焦虑，大多数源于自己用别人的标准来过生活吧，总会有人比你在某一方面更加努力，我们每个人，都可以在自己擅长的领域，达到投入和产出的平衡。
“信息化世界，我们很容易被他人的选择影响，去选择某个专业，追逐某个风口；
但我们的人生，真的不必总是做和别人一样的事情。”
[抱抱]
嘴太笨了，常常因为表达不到位而说不明白话，所以面对需要安慰别人的时候，只是安静的看着别人难过，看起来会有些不近人情。
好想跟大家说别难过啦，慢慢加油吧。
喜欢最近看的文章，其实对于内卷的焦虑，大多数源于自己用别人的标准来过生活吧，总会有人比你在某一方面更加努力，我们每个人，都可以在自己擅长的领域，达到投入和产出的平衡。
“信息化世界，我们很容易被他人的选择影响，去选择某个专业，追逐某个风口；
但我们的人生，真的不必总是做和别人一样的事情。”
[抱抱]
嘴太笨了，常常因为表达不到位而说不明白话，所以面对需要安慰别人的时候，只是安静的看着别人难过，看起来会有些不近人情。
好想跟大家说别难过啦，慢慢加油吧。
王浩先生在1961年提出了王氏拼块(Wang tiles)的概念，图一是一个王氏块的例子，其中用了5种颜色，拼块组里有13个拼块。王氏块的拼合规则是：不准转动，不准翻转，两块可以拼合仅当拼合处的两边有相同的颜色。图一最下面就是一个9*9的铺嵌例子。
给定一个王氏拼块组，很容易将其“按颜色拼合”的规则改造成按边上凹凸形状拼合的普通拼块组：先把上下方向和左右方向的使用的同种颜色分开，看作不同颜色（这样拼块就无法转动，转动后就不可能和其他已经放好的拼块拼合），然后每种颜色对应一种不同的凸起/凹进的形状，规定朝右和朝上是凸起，朝左朝下凹入（这样拼块无法翻转）。所以王氏块可看作是一种特殊的普通拼块。
王氏块中的多米诺问题是问，一组（有限块）王氏块能否铺满整个平面的问题是否可判定？也就是说，能不能写出一个程序来，输入任意一组王氏块，这个程序能在有限时间内回答，这组王氏块是否能铺满整个平面。
王浩最开始猜想，如果一个王氏块组能铺满平面，那就一定能用它周期地铺满平面（也就是不存在反周期的王氏块组）。如果这个猜想成立，那么多米诺问题就是可判定的。
为什么呢？因为如果一个王氏块组能周期地铺满整个平面，我们就一定能找到某个m*n的大块，这个王氏块组能把这个大块铺满，并使得它的左右两侧的颜色链是一致的，上下两侧也一样（这个结论证起来不难，有兴趣的可以试试），于是这个大块自己和自己是可以拼合的，铺满整个平面的事情其实就是把这个大块上下左右不断复制粘贴。所以我们的程序就只要不断地对这组王氏块拼成k*k的大块（k=1,2,3,……）的所有可能性进行搜索。如果上面所说的左右和上下颜色链一致的m*n大块是存在的，它总会出现在某个k*k大块里，于是我们就知道周期铺嵌是可能的，要么周期铺嵌不存在（于是按照王浩的猜想，它无法铺满整个平面），于是就一定存在某个k*k大块，这个王氏块组无法铺满，那么此时我们就知道这个块组无法铺满整个平面。所以这个程序真能判定多米诺问题。
（这里有些朋友会有疑问：有没有这样的可能性，某个王氏块组可以铺满任意大的有限的k*k大块，却无法铺满整个平面？不会的，这是图论中Kőnig引理的应用。这个引理乍一看平平无奇，一应用却很反直觉，这源于它证明中的非构造性。）
但是1966年王浩的学生Robert Berger写了一个小册子，证明了多米诺问题是不可判定的。这个证明的技术性很强，但是其中的思想却是非常简单，就是图灵机的停机问题，我们知道停机问题是不可判定的。Berger对每一个图灵机构造了一组王氏拼块，使得拼块的过程就是图灵机运行的过程：每块拼块可以看作是图灵机纸条上的一格，水平方向的每一行拼块就是某一给定时间里图灵机的纸条（以及图灵机读写头所在处和其状态），图灵机的运行规则（从读写头所处状态+在当前纸条上读到的字符决定下一步是要左右移还是要在纸条上写，或是停机）则由上下边上的颜色来表示。只要在平面的(0,0)处放上第一块表示图灵机初始状态的拼块，向右方的拼合方式是唯一决定的，每一块拼块放置好后，向它上方的拼合方式也是唯一决定的（即图灵机运行到下一刻的状态）。
这样，如果此台图灵机是不会停机的，那么向右和向上的拼合也是不会停止的，于是这个拼块组就可以铺满整个平面（因为它可以拼出任意大的有限大小的块来）；而如果此台图灵机是会停机，则拼合过程就会停止，拼块组无法铺满整个平面。于是拼块组能否铺满整个平面的问题等同于停机问题，于是不可判定。
而这就推翻了王浩最初的猜想，我们于是就知道，必定存在一个反周期的王氏拼块组：它可以铺满整个平面，却无法周期地铺满整个平面。
Berger最初找到的那个反周期拼块组中不同的拼块数量高达20426块，但很快这个数量就降下来了。 2015年Emmanuel Jeandel和Michael Rao找到了两组11块4色的反周期王块组；他们又用计算机穷尽搜索的方法证明了少于11块，或是少于3种颜色的王块组都不可能是反周期的，所以11块4色的反周期王块组是最小的。
如果不限于王氏块，那么反周期拼块组里的块数当然还可以更少。比如彭罗斯P3拼块组只有两块。是不是存在只有一块的反周期拼块组？这就是Einstein问题，和爱因斯坦本人无关，只是因为爱因斯坦这个姓的意思就是“一块石头”的意思。Socolar和Taylor在2011年发现了一种只有一块的反周期拼块组，但是它不满足普通的拼块条件，或者它是象图二所示表现为非单联通的图形，或者它需要一个和非相邻拼块有关的铺嵌条件。
而关于不可判定问题，前面我们说的是一般的多米诺问题无法判定，也就是没法写一个程序来判定任给的一组王块能否铺满平面，但是如果我们限定组中拼块块数或颜色数呢？显然，Jeandel和Rao的结果表明，11块以下，或4种颜色以下的王块组多米诺问题是可判定的。至于一般的拼块，2008年Nicolas Ollinger找到了一种构造固定的5块拼块来模拟任意王块组的方法，于是5块或以上的普通拼块（可以限制在所谓的Polyominoe类型内）的多米诺问题是不可判定的。Ollinger的文章名字：Tiling the Plane with a Fixed Number of Polyominoes，极易看懂，相当有趣，那5块拼块他命名为：肉、颌、馅、线、牙，都很形象（图三）
给定一个王氏拼块组，很容易将其“按颜色拼合”的规则改造成按边上凹凸形状拼合的普通拼块组：先把上下方向和左右方向的使用的同种颜色分开，看作不同颜色（这样拼块就无法转动，转动后就不可能和其他已经放好的拼块拼合），然后每种颜色对应一种不同的凸起/凹进的形状，规定朝右和朝上是凸起，朝左朝下凹入（这样拼块无法翻转）。所以王氏块可看作是一种特殊的普通拼块。
王氏块中的多米诺问题是问，一组（有限块）王氏块能否铺满整个平面的问题是否可判定？也就是说，能不能写出一个程序来，输入任意一组王氏块，这个程序能在有限时间内回答，这组王氏块是否能铺满整个平面。
王浩最开始猜想，如果一个王氏块组能铺满平面，那就一定能用它周期地铺满平面（也就是不存在反周期的王氏块组）。如果这个猜想成立，那么多米诺问题就是可判定的。
为什么呢？因为如果一个王氏块组能周期地铺满整个平面，我们就一定能找到某个m*n的大块，这个王氏块组能把这个大块铺满，并使得它的左右两侧的颜色链是一致的，上下两侧也一样（这个结论证起来不难，有兴趣的可以试试），于是这个大块自己和自己是可以拼合的，铺满整个平面的事情其实就是把这个大块上下左右不断复制粘贴。所以我们的程序就只要不断地对这组王氏块拼成k*k的大块（k=1,2,3,……）的所有可能性进行搜索。如果上面所说的左右和上下颜色链一致的m*n大块是存在的，它总会出现在某个k*k大块里，于是我们就知道周期铺嵌是可能的，要么周期铺嵌不存在（于是按照王浩的猜想，它无法铺满整个平面），于是就一定存在某个k*k大块，这个王氏块组无法铺满，那么此时我们就知道这个块组无法铺满整个平面。所以这个程序真能判定多米诺问题。
（这里有些朋友会有疑问：有没有这样的可能性，某个王氏块组可以铺满任意大的有限的k*k大块，却无法铺满整个平面？不会的，这是图论中Kőnig引理的应用。这个引理乍一看平平无奇，一应用却很反直觉，这源于它证明中的非构造性。）
但是1966年王浩的学生Robert Berger写了一个小册子，证明了多米诺问题是不可判定的。这个证明的技术性很强，但是其中的思想却是非常简单，就是图灵机的停机问题，我们知道停机问题是不可判定的。Berger对每一个图灵机构造了一组王氏拼块，使得拼块的过程就是图灵机运行的过程：每块拼块可以看作是图灵机纸条上的一格，水平方向的每一行拼块就是某一给定时间里图灵机的纸条（以及图灵机读写头所在处和其状态），图灵机的运行规则（从读写头所处状态+在当前纸条上读到的字符决定下一步是要左右移还是要在纸条上写，或是停机）则由上下边上的颜色来表示。只要在平面的(0,0)处放上第一块表示图灵机初始状态的拼块，向右方的拼合方式是唯一决定的，每一块拼块放置好后，向它上方的拼合方式也是唯一决定的（即图灵机运行到下一刻的状态）。
这样，如果此台图灵机是不会停机的，那么向右和向上的拼合也是不会停止的，于是这个拼块组就可以铺满整个平面（因为它可以拼出任意大的有限大小的块来）；而如果此台图灵机是会停机，则拼合过程就会停止，拼块组无法铺满整个平面。于是拼块组能否铺满整个平面的问题等同于停机问题，于是不可判定。
而这就推翻了王浩最初的猜想，我们于是就知道，必定存在一个反周期的王氏拼块组：它可以铺满整个平面，却无法周期地铺满整个平面。
Berger最初找到的那个反周期拼块组中不同的拼块数量高达20426块，但很快这个数量就降下来了。 2015年Emmanuel Jeandel和Michael Rao找到了两组11块4色的反周期王块组；他们又用计算机穷尽搜索的方法证明了少于11块，或是少于3种颜色的王块组都不可能是反周期的，所以11块4色的反周期王块组是最小的。
如果不限于王氏块，那么反周期拼块组里的块数当然还可以更少。比如彭罗斯P3拼块组只有两块。是不是存在只有一块的反周期拼块组？这就是Einstein问题，和爱因斯坦本人无关，只是因为爱因斯坦这个姓的意思就是“一块石头”的意思。Socolar和Taylor在2011年发现了一种只有一块的反周期拼块组，但是它不满足普通的拼块条件，或者它是象图二所示表现为非单联通的图形，或者它需要一个和非相邻拼块有关的铺嵌条件。
而关于不可判定问题，前面我们说的是一般的多米诺问题无法判定，也就是没法写一个程序来判定任给的一组王块能否铺满平面，但是如果我们限定组中拼块块数或颜色数呢？显然，Jeandel和Rao的结果表明，11块以下，或4种颜色以下的王块组多米诺问题是可判定的。至于一般的拼块，2008年Nicolas Ollinger找到了一种构造固定的5块拼块来模拟任意王块组的方法，于是5块或以上的普通拼块（可以限制在所谓的Polyominoe类型内）的多米诺问题是不可判定的。Ollinger的文章名字：Tiling the Plane with a Fixed Number of Polyominoes，极易看懂，相当有趣，那5块拼块他命名为：肉、颌、馅、线、牙，都很形象（图三）
✋热门推荐