读书笔记(十九)天语物道–李政道评传

 

作者:杨超

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

《天语物道–李政道评传》是一本2017年底2018年初新出的书,作者赵天池为实验物理学家,他是1981年通过李政道主办的中美联合培养物理类研究生计划(CUSPEA)考试赴美留学的。受李政道影响,后面还有生化类的留学计划等,开启了改革开放后我国新一轮的留学热潮。科普作家“土摩托”袁越也写过文章说自己得益于此。

该书花了很大的篇幅讲了李政道的家族史,从他的曾祖父开始。而李政道的求学经历则比较波折,随着抗日战争的扩大,他从小学起就不断转学,小学中学大学都没有毕业。先后转入上海租界区、浙江衢州、江西赣州,考入迁到贵州湄潭县的浙江大学,最后大二转入西南联大。大学未毕业,经吴大猷推荐,通过“种子计划”留学美国。因此,李政道说过:

在赣州那段孤独无助的岁月,在敌机轰炸之下的逃难路上,环境再危险再艰苦,还是想办法要鼓励自己生存下去。怎么鼓励自己呢?每一个个人都有生存的意义。都是生命,可我跟蚂蚁不一样,我可以了解这个宇宙怎么演变的,世界万物遵循什么规律,而蚂蚁不能。

由于传记的作者是物理学家,对李政道研究工作作了科普性的介绍。1949年,李政道的博士毕业论文是关于白矮星的理论,那时人们尚未知道白矮星是恒星演化的晚年阶段。之后,李政道的研究领域涉及弱相互作用、统计力学、湍流等等。

其中,书中对李政道和杨振宁合作的关于弱相互作用宇称不守恒的获诺贝尔奖的工作更是深入浅出的介绍,来龙去脉讲得十分有趣。我读过一些基本粒子的标准模型的科普书,对此介绍较为简略,比如一般的只提到吴健雄的实验证实了宇称不守恒。读了此书,才知道几乎同时还有另外三组科学家也通过不同的实验独立验证。即一共有四组独立实验的验证,其中有三组是李政道直接推动的。

此外,作为最新的一本李政道传,难免花不少笔墨来介绍杨振宁以及李杨两人失和的原因,和否定杨建邺著《杨振宁传》的一些说法。至于那种说法更接近真实情况,只能由读者去判断了。

但无论如何,李政道和杨振宁都是伟大的中国物理学家,都非常爱国。通过两人的学术风格,我感觉到,李政道偏向于实用主义,他为发展中国的物理事业的工作面更广,如CUSPEA和很早就回国作实实在在的讲学等。杨振宁更加理想主义,就如他的工作更偏爱数学的美,加入美国籍成了他的一个心结,自己多次写文章谈到这个问题,谈到他父亲心底一定不会原谅他放弃中国国籍。2015年,杨振宁放弃美国国籍,重新加入中国籍,算是解了这个心结吧。

如同作者在自序中指出的,本书唯一的遗憾就是对李政道1962年后的研究工作和事迹介绍较少,几乎是一笔带过。

发表在 读书 | 留下评论

读书笔记(十八)Four Colors Suffice

 

作者:杨超

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

我给大一的学生在《离散数学》课程上讲述图的染色理论以及五色定理的证明很多年了,但是对四色猜想得到证明的历史过程没有深入了解过。最近读了Robin Wilson著的《Four Colors Suffice》一书,是2002年出版的较新的讲述这一历史过程的科普性作品,读来十分有趣,利用4天的闲暇时间一口气读完了。

此书既讲述历史,也讲述证明,基本把整个证明的原理讲得非常清楚明白了。而且把我知道的许多图论及相关数学知识在证明四色猜想这个故事背景中串联起来,读来津津有味;也有许多内容是第一次读到,给人带来启发。

下面列举一些我从该书获得的印象比较深刻的知识点:

  1. Tempe的错误证明细节,11年后才被发现;
  2. Tait的错误猜想(任何三连通三正则平面图有Hamilton圈)如何同四色猜想建立联系;
  3. 布鲁克黑文实验室的日本人Yoshio Shimamoto 一度差点以为也得到一个只需一个reducible 构形的简单证明;
  4. 四色猜想除了向k的亏格的曲面推广外,还有一个每个国家可以有最多n个不连通区域的推广,都完全解决了;
  5. Haken在 unknotting  problem上也作过重要贡献;图的染色多项式有些奇怪特点(不久前去年才在Quanta上看到韩国人June Huh也在chromatic polynomial上作了重要工作);C-reducible和D-reducible的定义搞清楚了;
  6. 了解了American J. of Math.这一期刊,以前看fifteen puzzle的历史也看过该期刊的文章;
  7. 原则上四色猜想也可以转化成一个方程组问题,虽然可能这组方程并不好解;
  8. 首创 discharging 方法的Heesch在平面tiling问题上也有贡献;
  9. 当时四色猜想的研究还是很热门的,是不少博士论文的研究题目,有好几组研究者都试图用计算机方法证明;Haken和Appel主要是在先找一组 unavoidable 构形的策略上取胜。

总之,非常好的一本数学通俗读物,当然书里面的很多数学证明也不见得容易读懂。

 

发表在 数学, 读书 | 留下评论

《花之谜题2》

 

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

除了推箱子,能令人饶有趣味地玩的益智类游戏不多。六年前玩过的《花之谜题》便是其中之一(2011年就开始玩了,博文写于2012年)。

今年(2017年)8月,惊喜地发现,时隔六年,《花之谜题2》出来了,有35个新关卡。于是从itch.io网站下载了2代,并支付作者2美元,以感谢作者设计出如此有趣的游戏。顺带用下paypal支付。如今网上的海外支付都越来越多支持微信和支付宝,用到paypal的机会不多了。

 

 

发表在 游戏 | 留下评论

2017年第一届广州黄埔马拉松

 

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

现在的黄埔区(广州开发区)是2014年萝岗和黄埔合并后的新黄埔区。举办比赛的路线基本属于原萝岗区的地盘,在2005年萝岗区设立之前则是属于白云区管辖。这一带我基本没有去过,离市中心比较远。之前去过离赛事起点最近的地方是岭南职业技术学院代课,需要先坐地铁到黄村站,再转公交。

一、报名

2017年9月27日,得知今年的广州马拉松的半马项目报名没有中签。9月30日,通过微信公众号“第一赛道”成功报名了第一届黄埔马拉松。报名方式是先导先得,以支付成功为准。通过微信支付了100元报名费。黄埔马拉松是由广州中体体育运营,之前参加过该公司运营的清远马拉松。该公司运营的另一比赛容桂半马也报名过,但遗憾最后弃赛。

(中体体育logo)

中体体育目前还运营桂林、百色等地的马拉松,主要集中在两广地区。

二、取消?

广马前一天,得知同是中体体育承办的2018年元旦顺德容桂半马取消。12月13日,黄埔马拉松官网放出《关于2017广州黄埔马拉松赛因故取消不实传言的严正声明》的公告。

10月初也有新闻报道,万达体育曾宣布其旗下的Rock ‘n’ Roll马拉松要在2017年12月31日举行广州站。万达集团官方微博直到11月1日还宣称有摇滚马拉松广州站。我还想着要报名呢,但后来也没有后续消息了。这个摇滚马拉松在今年的10月28日举行了中国的第一站:成都站。

之前也听魏老师提起过黄埔马拉松因安保问题可能要取消,也许她指的是摇滚马拉松广州站吧。

(关于摇滚马拉松广州站报道的网页截图)

总体来说,马拉松赛事继续稳步增加,已有的赛事也越来越规范(如经中国田协CAA认可)。粤西地区,2016年起已有由中体体育承办的阳江海陵岛马拉松。又得知今年2017年12月16日,茂名在市区近郊露天矿生态公园举办了半马,还是用了智美集团旗下智能体育的芯片。不知这一赛事能发延续下去。更西的湛江则未听闻办过半马或以上的正规赛事。

三、领装备

12月21日,中午抽空到广州国际体育演艺中心领取了装备。坐地铁到6号线萝岗站,单程要大概1小时20分钟。加上领装备,来回足足花了3个多小时。

比赛T恤是我之前从未听过的福建品牌:奔泰。号码布芯片则是芝华安方提供,不知是否已经采用国产技术了,之前芝华安方用的多是ChampionChip的鞋带芯片。另有一个手环,说是要佩戴作为检录入场凭证,这是我第一次见到这种方式。

参赛包还有一本《城市马拉松》杂志,是借《旅游新报》(CN50-0013)刊号发行的。另外比较有特色的就是发了一盒洗衣液套装,市场价值几十元,可以说是值回报名费了。还有广氏菠萝啤一瓶,回来后就喝了。其它还有些优惠券等就略去不提了。

四、比赛日

12月24日早上5点20起床。6点刚过打的到比赛地点,由于赛道封路,折腾了一会。比较远,花了111元。马上存衣,走了较长一段路到起跑区等候,才7点多,有点早。也许坐免费地铁更好。

8点开跑,全马人不多,只用了2分多就通过起点。小坡(含隧道)较多,最后自己虎扑跑步APP录得2小时1分58秒完赛,未能破二,有点失望。前11公里约用1小时,后面实在没有力气跑了,降到6分配速,还是跑量较少。

领取完赛包和存衣包后,就坐免费地铁回来。因为远,到家都快12点了。收到短信,枪响时间2小时4分23秒,净时间2小时2分1秒。

中午饭后又溜一会娃,的确是累。

五、赛后

第二天腿还是有点酸,尤其大腿前后侧,但程度比上上周广马低。第三天酸痛基本完全消失。

12月25日傍晚下载到电子证书,男子组枪声成绩排903名,净时间排1077名;算上女子则枪声成绩排968名,净时间排1168名。

mlszp和爱云动两个网站均找不到照片。

 

发表在 健身 | 留下评论

2017年第六届广州马拉松

 

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

一、报名

广马今年取消了5公里,全马和半马的报名时间段也分开。8月22日,在官网预报名。9月27日,查到抽签结果不中。

之后陆续参加了中国马拉松大满贯、益跑网、最酷网、花城FM微信号等广马合作伙伴的名额免费送活动,均未中奖。中国马拉松大满贯是中国田径协会今年新设立的系列赛事品牌,2017年只有北京马拉松和广州马拉松两站。加上2018年的重庆、武汉、北京三站,将构成中国马拉松大满贯的首个2017-2018赛季。

另广马在去年成为国际田联IAAF铜标赛事之后,今年进一步升级为IAAF银标赛事。

智美集团亦把其运营的马拉松比赛包装成“奔跑中国”品牌,今年包括“红色之旅”和“改革开放”两大主题共十六站。前者有上海(崇明岛)、遵义、延安、吉林、北京、襄阳、南昌、长沙8站,后者有昆明、沈阳、南京、杭州、青岛、防城港、广州、深圳8站。广州是第十五站,最后一站深圳马拉松下周举行。另外,智美还协办了一些城市马拉松没有列入此系列,如东莞、南宁等。

广马的“帽子”越来越多了。

11月16日,又得知广州市慈善会联合广马组委会有慈善方队名额,深夜按规则捐了2000元确保了半马名额。

11月19日,收到广州市慈善会的电子邮件、短信和电话多重通知,用收到的邀请码在广马官网报名半马项目成功。一共只有34名全马和13名半马慈善选手报名了。

二、路线

过去三年的第三、四、五届广马我都参加了,路线基本没有变化。今年组委会裁判组成员魏老师在微信中向我征询对广马的建议。我提到其中一点就是:起跑从花城广场上主路有个瓶颈。

之后比赛路线公布后,发现改从天河体育中心出发,看来我的意见也发挥了作用。前几年,天河体育中心是作为5公里项目的终点,今年取消5公里,正好可以作为起点。

由于起点变了,车陂南折返点提前。另外过猎德大桥后路线略有改变,这样半马完全避开了琶洲隧道。

三、插曲:院运会

今年院运会安排在广马前一周的周日12月3日。由于某种原因,不是我院单独举办,而是数地文史哲五院联办。连续四年参加院运会1500米后,今年首次没有参加任何个人项目。只是稍微玩了一下卧推和引体向上,参加了教工拔河比赛。

四、领装备

12月7日,到天河体育馆领取装备。前几年都是在天河体育中心南广场领取。今年因南广场作为赛事起点,同时要进行起点的布置,所以领物地点就稍微挪动一下。

我先领取了号码布。之后凭号码布领取了T恤和其他物品。计时芯片由智美集团旗下的智能体育提供(去年也是,再之前两年都是芝华安方,其中2014年第三届甚至需要还芯片退押金,可见计时芯片行业变化很快)。然后又到广州市慈善会的摊位领取了纪念品。

这次广马,短信领物通知还给出了一个链接,是dpxian.me(地平线)提供的电子比赛手册。于是,除了纸质版比赛手册,还很方便地可以在手机上看比赛起点集结的相关信息。

五、插曲二

比赛前几天,正是广州举办《财富》全球论坛的日子,安保明显加强。还好没有影响到广马的正常举办,看来广马本身的商业利益也足够大。

赛前一天,又听闻中体体育承办的2018年元旦的容桂半马取消了,不知道是什么具体原因。另一个中体承办的广州市黄埔马拉松会如期举行吗?

六、比赛日

12月10日,距上一次跑半马2016年12月11日广马,差一天就整整一年了。早上和同事蔡教授相约6点20分在地铁站汇合,我骑摩拜单车抵达,这还是搬家后首次参加路跑比赛。坐地铁到体育中心站出来,然后脱去外套后寄存存衣包,人较多。

天气预报说早上最低10度,但是脱去外套后短衣短裤丝毫不觉得冷,也许因为无风、干燥且天晴的缘故吧。比起2014年珠海半马,2016年香港半马暖和多了。

在天河主体育场外环形道路候跑,上体育场二楼平台厕所方便了一次。

这次的装备从下到上为:李宁跑鞋力为袜子力为运动短裤(兜里装钥匙)官方特步比赛T恤、EZON手表、华为手机(用虎扑跑步记录)。因为广马期间地铁免费,且手机启用了NFC地铁云卡,所以决定不带羊城通和零钱。今年习惯了手握手机跑步,所以腰包也不带了。而无GPS功能的新EZON手表计时最多只能99分钟59秒,完全不起作用,下次也不用带了。现在智能手机的功能越来越强大,其支付和运动轨迹记录功能替代了现金和GPS手表,使得以后跑步比赛可以更加轻装上阵。

本届改进后的赛道普遍没有极端拥挤路段出现,除了临江大道折返前一段不知是修路还是什么原因有围蔽,略显狭窄。考虑到全马有18000名额,半马紧跟着全马后面出发,赛道线路的改变规划还算可以。

这次饮水点在路两旁都有,我全程一共靠边取水或饮料四次。初中体育老师魏老师作为广马技术官员,还是在17.5公里处带领志愿者提供饮水。我放慢速度经过没看见魏老师,后来才知道她在前进方向左手边,我只看了右手边。

最后自己记录到2小时2分31秒完赛,比我赛前根据身体主观感觉评估的2小时6分还要快。全程基本匀速,据跑步软件的记录,只有第1公里起跑、第9公里临江大道折返、第18公里饮水点配速是6分多一点。在年跑量只有200多公里的训练强度下,比去年广马只慢了1分多,还是相当满意的。可能平时常常抱着儿子连续走路也有一定的有氧训练效果。

过终点后,喝了一瓶饮料,快速取了完赛包和存衣包,在广州市慈善会背景板前自拍一张,就坐地铁离开了。完赛包里面照旧有毛巾。第二次完赛后发了一根带盒子的都乐香蕉(上次是今年的广州10k)。其它还有饮料等。

七、赛后

10点半左右就回到家。中午、下午两次抱着儿子出去散步晒太阳,还是有点累,下台阶腿略有点酸,主要是膝盖周围。晚上睡的很沉,第二天醒来大腿则有明显适度的酸疼。第三天基本恢复,酸痛基本消失。

赛后没有受到短信成绩,12月11日早上,我才又从地平线网站(就是前面提到的提供电子赛事手册的网站)上查到第3302位通过起点,第1727名过终点,官方净时间为2小时2分32秒。11日晚上,又在官网下载到完赛证书,净时间则为2小时2分33秒,排名为1626。

至于照片,马拉松照片网(mlszp)只有5张,照得一般,又贵,今年不买了。跑步维生素(runff)也只有3张,也是人多表情一般,只下载了带水印版本。爱云动则有16张,下载了16张,并且答谢了其中两张,下载到高清原图,花了共16元。还试了下爱云动的人脸识别找照片功能,效果比按号码查差一些。感觉爱云动这个后起的马拉松照片分享平台的技术迅速超越了mlszp和runff这两者。

12月14日,看到mlszp网上我的照片又更新了,多了几张。忍不住还是买了一张的电子版。这次几分钟后就能下载,购买体验比之前略好了一些。

 

发表在 健身 | 留下评论

2017年中山大学运动会环校长跑和100米

 

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

上一次参加校运会是2015年,去年没有参加。10月28日碰见学院书记,他对我说:杨超你要报名校运会。于是我就又一次报名100米。

11月19日,早上7点起床。8点到达中大北门。今年的环校长跑路线略有改变,距离长了一点点达到2公里。但这种集体慢跑速度起不来,相当于散步。

开幕式后,11点参加了100米。第二次参加校运会100米,成绩为15秒13,比前年还慢。平时很少练这种短距离全力冲刺跑,感觉就是难以积极调动力量和摆腿频率。

发表在 健身 | 留下评论

跑步总结:第八个半年

 

本文地址: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甚至指出,若限制只有有限个箱子没有归位(其余可数个箱子一开始都处于目标点),问题仍然是不可判定的,或者说是不可计算的。

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

 

 

 

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

王浩瓷砖(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。我觉得不太可能。

 

 

 

 

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

量子计算机能快速求解推箱子关卡吗?

 

作者:杨超

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

量子计算机常被大众媒体描述得十分神奇,甚至有科学家也添油加醋,如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗?我在读了David Deutsch的书后,对此问题颇感兴趣。这个月,阅读了不少相关文献,找到了答案。答案是否定的。

首先,制造出通用的量子计算机仍然有极大的工程技术困难。

第二,再看看理论上,量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法,这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出(Shor因此获得哥德尔奖Godel Prize),历史也没有太长。想要知道这一算法与传统计算机算法有何不同,可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年,才36岁,是德州大学奥斯汀分校的教授,在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律,量子算法恰恰能更好地利用这一规律,一定程度上避免了暴力穷举。

要注意的是,整数分解并非特别难的问题。在基于传统计算机(图灵机)的计算复杂度理论中,整数分解被认为不属于P,但也只是比P问题略难一些,介于P和NP-Complete之间,且更靠近P。因此,量子算法能快速分解大数也只是情理之中。

知道量子算法是怎么做的,能做什么,就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话,澄清大众对量子计算的误解:

If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

这句话翻译过来就是:如果你想从我的博客中只学一样东西,那就是量子计算机无法通过同时尝试所有可能来求解困难的搜索问题。

这句话简直是针对本文开头的问题的完美回答。就算大规模的量子计算机制造出来了,NP完全问题也不可能有快速算法,更不用说比NP完全问题更难的推箱子(PSPACE完全问题)了。

第三,有和没有快速算法(efficient algorithm)的分界线在哪里呢?Scott Aaronson在NP-complete Problems and Physical Reality一文(发表在2005年ACM SIGACT News)中也有深刻独特的见解。除了量子计算,他还逐一考察了蛋白质计算等若干未来可能有物理实现的计算机模型。文章最后,他给出了如下的一条分界线:

基于图灵机提出的P问题类也许未能很好的刻画有快速算法问题全体。具有快速算法的问题应该更广泛些,包含整数分解和图同构等。这也许是一条深刻的物理规律。

 

 

发表在 推箱子, 数学, 算法, 计算机 | 留下评论