『天问:世界观的对话』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块拼块他命名为:肉、颌、馅、线、牙,都很形象(图三)
✋热门推荐