关卡无限大的推箱子

 

作者:杨超

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

通常我们玩的推箱子关卡都是有限大小的,一般不超过50×50。因为最近读了不少关于不可判定(undecidable)问题的文章,很自然就问这样一个问题:我们已经知道有限大小的推箱子问题是可判定的,且知道其计算复杂度为PSPACE-complete;若考虑无限大小的推箱子关卡,即关卡占据整个平面,允许有可数无限个(countable)箱子和目标点,那么问题是不是也变成了不可判定的?

比较著名的不可判定问题有:

  • 图灵机的停机问题;
  • 希尔伯特的Entscheidungsproblem问题,即一阶谓词逻辑系统的判定问题;
  • 王浩瓷砖(Wang Tile)问题;
  • 希尔伯特第十问题,即判定丢番图问题是否有解;
  • 计算Busy Beaver数;
  • 元胞自动机(Cellular Automata)的可逆性;
  • ……等等。

现在,我们可以给这个列表又添加一个新问题:无限大小的推箱子问题。这个结论,早在1997年,Culberson证明推箱子是PSPACE完全问题时,就顺带指出了。因为Culberson的证明就是用推箱子关卡来模拟图灵机,从而把LBA问题(线性空间的图灵机)归约为推箱子问题。在往前走一步,自然任何一个潜在无限长纸带的图灵机也可以用占满整个平面的无限大小的推箱子关卡来模拟,从而把停机问题归约为推箱子问题。

这就证明了关卡无限大的推箱子是不可判定的。Culberson甚至指出,若限制只有有限个箱子没有归位(其余可数个箱子一开始都处于目标点),问题仍然是不可判定的,或者说是不可计算的。

这从另外一个方面也体现了推箱子有多难。

 

 

 

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