月归档：十月 2017

  本文地址：http://sokoban.ws/blog/?p=3868 最近六个月跑量如下： 2017年5月：36公里（珠海4周+广州10k+别克10k） 2017年6月：30公里（珠海5周） 2017年7月：0公里 2017年8月：5公里（环合肥翡翠湖） 2017年9月：0公里 2017年10月：25公里（下班跑回家1.5k共5次+校园中轴线3k+英东体育场5k共3次） 半年合计：96公里 体重变化如下： 经过一个学期珠海跑步，6月底体重降到60公斤以下。7月底59公斤左右；8月底60+公斤；国庆长假后一度63+公斤；10月底62+公斤。 手表 两个GPS手表已经坏了多时，今年的跑步几乎全部都是使用手机APP虎扑跑步来记录。 于是，10月又买了个100多元的EZON石英表，福建产，只具备一般的跑表功能。另有电波校时功能，能接受商丘授时中心的信号，在23层楼顶测试手动校时成功（石英表已经极其准了，校时一次就可以长时间关闭每天自动电波校时功能）。之前使用过卡西欧的日本电波表，才知道原来我们也有民用电波授时。  

  作者：杨超 本文地址：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甚至指出，若限制只有有限个箱子没有归位（其余可数个箱子一开始都处于目标点），问题仍然是不可判定的，或者说是不可计算的。 这从另外一个方面也体现了推箱子有多难。