月归档:九月 2017

王浩瓷砖(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 … 继续阅读

发表在 数学, 计算机 | 留下评论