王浩瓷砖(Wang Tile)

 

作者:杨超

本文地址:http://sokoban.ws/blog/?p=3795

王浩(Hao Wang)是著名的美籍华人数学家、逻辑学家、哲学家。他1921年生于山东济南,1943年毕业于西南联合大学,1948年在美国哈佛大学获得哲学博士学位,1995年在美国纽约逝世。王浩是哥德尔(Kurt Gödel)的好朋友。创立了NP完全理论、证明了SAT是第一个NP完全问题的著名计算机学家Stephen Cook,则是王浩的学生。

王浩(1921-1995)

为了研究一阶谓词逻辑的可判定性问题(即希尔伯特的Entscheidungsproblem问题),1961年,王浩提出了瓷砖问题,后来被他的学生Robert Berger称为王浩瓷砖(Wang Tile)问题。任意给定一组有限个正方形的瓷砖,每个瓷砖的每条边都用一种颜色标记。用这组瓷砖去铺整个平面,每种瓷砖都有无限的供给。要求铺设时,任意两块瓷砖相邻的边的颜色要相同。并且,只允许瓷砖平移,不能够旋转或者镜面反射。王浩问:能否用这组瓷砖平铺整个无限的平面?

如下图是一组13个正方形的王浩瓷砖。

如下图那样平铺。

自王浩在1961年提出瓷砖问题,直到今天还引出许多研究。可以说这是一个非常有趣而深刻的问题。

一开始,王浩猜测,任意给定一组瓷砖,要么可以铺满整个平面,并且一定有一种周期的平铺方案;要么不能平铺整个平面。如果这个猜测是对的,那就意味着存在一个确定性的算法去判别每一组王浩瓷砖是否可以铺满整个平面。

王浩还发现了王浩瓷砖可以用来模拟图灵机。由此,王浩证明了,若对王浩瓷砖问题作出一些限制,如原点必须铺某一块瓷砖,或是坐标轴上的瓷砖预先铺设好等等,则王浩瓷砖问题是不可判定的(undecidable)。即不存在确定的算法去回答平铺是否能够实现。

从可计算性和计算复杂度看来,王浩瓷砖问题远远难于PSPACE完全的推箱子问题(Sokoban)。因为王浩瓷砖问题是不可计算的。而推箱子问题是可计算的,而且在可计算的问题里面,推箱子问题也远还不是最难的。

不久,1964年,王浩的学生Robert Berger在其博士论文The Undecidability of the Domino Problem中证明了即使没有对原点或是坐标轴的限制,王浩瓷砖问题(无限制的王浩瓷砖问题又被称为domino problem)也还是不可判定的。Robert Berger的博士论文还发表在1965年的Memoirs of the American Mathematical Society。

为了证明domino problem是不可判定的,Robert Berger也构造出第一组只有非周期铺满方案(aperiodic tiling)平面的王浩瓷砖。但是,这组瓷砖由惊人的20426个瓷砖组成。这也否定了王浩认为总是存在周期性的铺满方案的猜测。

也就是说,不可判定的证明主要基于两个核心事实:一是只能非周期铺满平面的王浩瓷砖组(an aperiodic set of Wang tiles)存在;二是王浩瓷砖可以模拟图灵机。通过这两个事实,Berger可以把图灵机停机问题(Halting Problem)的每个实例归约为一组王浩瓷砖,使得停机问题的实例不停机当且仅的对应的王浩瓷砖组可以铺满整个平面。而停机问题是大家熟知的不可判定问题,从而王浩瓷砖问题也是不可判定的。

1971年,R.M. Robinson构造出一组非周期王浩瓷砖组只由60个左右瓷砖构成,从而大大简化的domino problem不可判定的证明。Robinson构造的非周期平铺方案有某种自相似性。这一研究发表在德国的Inventiones Mathematicae。若想知道不可判定证明的细节,可读读Robinson的文章。

之后的研究更多着重于寻找一组数目更少的非周期王浩瓷砖组。

到了1996年,Jarkko Kari用一种全新的方法,构造出一组非周期王浩瓷砖组只有14个不同的瓷砖。并且马上被Karel Culik II用同样的思路改进到只有13个。两篇文章都发表在Discrete Mathematics上。与Robinson的方案不同,Kari 和 Culik 的方案似乎不具有自相似性。

2015年,Emmanuel Jeandel 和 Michael Rao 通过系统性的搜索计算,找到一组只有11块的非周期王浩瓷砖组,并且证明不能更少了。这一成果还在同行匿名审稿中,手稿已经放上arXiv,但尚未正式发表。

王浩瓷砖问题是用正方形加上颜色匹配、通过平移去铺满平面的问题。若不局限于正方形、采取更多样的匹配规则、和允许旋转和镜面反射等,则可引出更多的研究问题。如Roger Penrose找到一组两个菱形瓷砖就可以迫使非周期铺满方案。Penrose的设计也可以通过在菱形基础上加入小凹凸匹配完全由形状确定匹配要求,如下图。

2011年 Socolar 和 Taylor 发表在JCTA的文章则只用一片正六边形瓷砖(如下图)就迫使非周期的铺满方案,但是用了非常复杂的匹配图案和允许镜面反射。

只用一片瓷砖,并且只用形状匹配(即不使用颜色线条等额外匹配要求),能否逼迫只能非周期铺满平面呢?这就是所谓 Einstein Problem。我觉得不太可能。

 

 

 

 

此条目发表在 数学, 计算机 分类目录。将固定链接加入收藏夹。