第二天,那个让程序去找程序的笨东西,江临终於给它取了个正经名字。
微程序搜索器(mps)。
听著像上个世纪的產物,但对江临来说,这就是个愿意把所有蠢办法都撞一遍,而且永远不会嫌烦的赛博苦工。
在量化这头,它现在已经能帮江临干不少脏活了。
帮他揪出那些藏在系统里,单次不起眼但每天被循环几千万次的热路径。
它还是个冷酷的质检员,新找出来的每一套做法必须和旧流程逐项比对,只要有一项输出对不上,立刻判死。
今天是五个数排名,明天可能是十六个数分桶。
而且,江临很快意识到,这玩意儿最有价值的地方还不是快那么一点点。
而是它在逼著自己变得更加严谨。
因为他在使用这个搜索器的时候,想要让它工作起来更加顺利,就必须明確告诉它。
什么算对,什么算错,什么边界绝对不能碰,什么动作看似捷径,实则是把未来的债挪到了现在?
这简直就是最硬核的自学过程。
【记住全网最快小説站 101 看书网解书荒,1?1???.???超实用 】
以往他学个新概念,总得在脑子里左右互搏。
一个状態压缩会不会丟信息?
一个递推是不是偷偷混进了未来数据?
一个看起来精妙无比的证明,会不会在某个极端边界上一脚踩空?
现在,相当於身边多了一个没有智商,但体力无限的死脑筋助教。
江临在终端里敲下一行测试:“这个说法在十个元素以內有没有反例?”
mps不懂为什么,它只会把所有情况像翻抽屉一样全倒出来。
如果没有,它告诉你在这个小范围里没找到。
如果有,它会把那个血淋淋的反例直接拍在你脸上。
足以让江临省下大把时间,去验证自己的直觉是不是错的。
但mps v0.1太直肠子了。
五个数的排序,代码跑得欢快。
六个数,后台列印的痕跡开始变得杂乱。
等到八个数,以及更大的数时,为了找出那条最短、最稳、最不容易出错的动作序列,它必须在海量比较顺序里试探。
机箱里的风扇一下子开始狂转,发出沉闷的嗡嗡声。
任务管理器的曲线上,cpu占用率瞬间顶在了100%。
路太多了。
所有可能的动作序列像决堤的洪水一样漫出来,直接把这个体力无限的工人淹死在了內存里。
靠剪枝撑出来的生机,在指数级的爆炸面前不值一提。
江临听著机箱的轰鸣,捏了捏眉心。
这是结构性的绝症。
已经不是多掛机几个小时能解决的问题了。
要让这套工具链成为核心,他必须解决更底层的逻辑。
哪些状態可以合併?
哪些死路可以提前砍掉?
以及砍掉之后,怎么在数学上证明自己没有误杀真正的最优解?
江临切回日誌文档,敲下几行字。
mpsv0.2目標:不再只会试,要学会合併状態,排除死路,证明剪枝合法。
写完,他停了一下。
光標在末尾有节奏地闪烁。
他又补上一行。
需要数学语言:局部规则,状態转移,全局约束。
这几个词,不知怎么地,就在他脑子里意外接上了另一条线。
让他想起了一个更老的问题。
如果一块形状的物理边界,就是一种天然的局部规则?
如果两次图形的严密拼接,就是一次状態转移?
错误接法会自动走进死路,而正確接法会被迫像长晶体一样,蔓延成越来越宏大的结构。
这跟他在机箱里让mps疯狂试错,本质上没有什么区別。
江临重新把光標放回搜索框。
这一次,他没搜代码,而是敲下了一行英文。
local rules force global structure
回车。
几秒钟后,页面上跳出了几个词:tiling(铺砌)、substitution(替代)、aperiodic(非周期)。
他顺著连结一路点进去。
penrose 铺砌、wang tiles(王氏砖)、准晶体。
最后,在一篇学术综述的边角处,他看见了那个如针尖般锐利的词。
monotile(单一瓷砖)。
江临盯著这个词看了足足半分钟,眼神发亮。
隨后在搜索框里重新输入:aperiodic tiling monotile。
……
下午,江临去了江大图书馆,借了四本书。
一本有限自动机,一本组合优化,一本符號动力系统。
以及一本封皮都有些卷边的离散几何讲义。
他想找一种证明方式,一种能说明有限的局部约束,怎样在无限扩展中仍然有效的数学语言。
翻到离散几何讲义的中间部分时,他的目光停在一个章节名上。
aperiodic tilings(非周期铺砌)。
他快速扫过。
先是 wang tiles,再是 penrose tilings,接著是 substitution tilings。
最后,在这一章快要结束的地方,讲义用极短的一段话提到了一个概念:
einstein problem: whether a single tile can force aperiodicity.
(爱因斯坦问题:是否存在单一形状的瓷砖,能迫使铺砌呈现非周期性。)
一块砖。
仅仅凭藉自身的几何形状,就能铺满无限的平面,但所有铺法永远不可能產生周期性的重复。
这简直就是mps思想完美的几何实体化。
程序里,局部动作排除错误路径,把搜索器逼进唯一的可行域。
几何里,一块砖的局部边界排除所有错误拼法,把无限的平面逼进一种深邃的层级结构。
一虚一实,严丝合缝。
江临合上那本封皮卷边的离散几何讲义,从图书馆出来的时候,脑海中依然盘旋著局部规则、状態转移和全局约束这三个词。
原本在微程序搜索器(mps)中遇到的状態空间爆炸问题,此刻在几何学的语境下,似乎被投射成了一个具象的实体。
穿过林荫道,他本打算直接去车棚取自行车回七中,余光瞥见路旁公告栏上的一张海报。
离散几何读书班
主题:非周期铺砌、准晶与单砖问题——局部规则,如何强迫出全局结构。
地点:数学学院c楼 216
主持:顾南舟(副教授)
时间:15:30
江临的脚步一下子停住了。
局部规则,如何强迫出全局结构?
想到mps里的核心困境,他摸出手机看了一眼时间,距离开班还有十分钟。
他当即取了自行车往数学学院骑去。
数学学院的c楼比物理楼要安静许多。
墙上贴著各类学术讲座的海报,大多充斥著张量,流形,同调群等词汇。
c216的门半掩著。
江临推门进去,找了最后一排靠窗的位置坐下。
教室不大,正中间拼著几张长条桌,十来个学生零散地坐著。
有人在翻看列印好的论文,有人在笔记本电脑上敲击。
气氛並不严肃,但似乎也没轻鬆到哪里去。
正前方的白板边,站著一个三十多岁的男人。
他穿著浅灰色的衬衫,袖口隨意地卷到手肘处,手里转著一支白板笔。
应该就是顾南舟。
投影仪亮著,幕布上打出一张错综复杂的几何图形。
正是经典的penrose(彭罗斯)铺砌。
图中只有两种基本形状。
一种是风箏,一种是飞鏢。
边缘都带有特定的箭头標记。
“我们今天討论非周期铺砌。在这之前,我需要先釐清一个经常被外界,甚至被部分初学者误解的概念。”
顾南舟转身在白板上写下一行字。
non-periodic≠random
“很多人觉得,非周期就是乱,就是没有规律。”顾南舟指著黑板上的等式,“隨机当然不具备周期性,但数学的美感从来不在於毫无章法的混乱。”
“彭罗斯铺砌之所以迷人,在於它的局部规则非常有限,甚至可以说非常简单,但它却能在无限延伸的过程中,不可抗拒地强迫出全局的非周期结构。”
他在白板上快速勾勒出风箏和飞鏢的轮廓,並在边缘重重地点出几个箭头。
“两块砖,只要加上这些匹配规则,规定箭头必须同向相接,你就永远无法拼出一个可以平移重合的周期图案,因为它被锁死了。”
坐在前排的一个博士生举起手,推了推眼镜问:“老师,彭罗斯铺砌依赖於边缘的匹配规则。如果我们在物理上实现它,比如把这些箭头做成真实的凹凸卡扣,把匹配规则直接內化到几何形状里,是不是就等价了?”
“直觉很准確。”
顾南舟讚赏地点点头。
“实际上,这正是后来很多构造法在做的事情。用纯粹的几何边界来代替人为附加的符號规则。只要形状设计得当,两块砖確实能做到这一点。”
说到这里,他的话锋忽然一转,语气沉了下来。
“但如果,我们將条件推到极限呢?”
他拿起黑板擦,將刚才画的风箏和飞鏢擦掉,重新写下三行简短的英文。
one tile
tiles the plane
only non-periodically
“单砖问题(the einstein problem)。这个名字不是指物理学家爱因斯坦,而是德语里的ein stein——一块石头,一块砖。”
顾南舟的目光扫过长桌边的学生,像是在拋出一个沉重的锚。
“只用一块砖,它能无缝且不重叠地铺满整个二维平面。但是,所有的铺法,都不可能產生周期性的重复。”
教室里出现了短暂的寂静。
“一块砖能铺满平面,这毫无难度,正方形,正六边形都可以。”顾南舟敲了敲白板,“难点在於,它必须没有任何周期铺法的可能。你不能说,我碰巧给它安排了一种花里胡哨的非周期拼法就算成功,那远远不够。”
他加重了语气:“你必须在数学上证明,任何人,哪怕他绞尽脑汁想要拼出一个周期性的图案,只要他拿著这块砖,他就逃不开非周期的宿命。这块砖的几何形状本身,必须成为一种暴政,一种强迫。”
坐在后排的江临,呼吸微微一滯。
立即翻开隨身携带的黑色笔记本,在空白页上写下一行字。
不是给出一种非周期铺法,而是强迫所有铺法进入非周期层级。
这是一种降维打击般的约束力。
也正是他的mps系统现在最缺乏的特性。
mps只是在海量的可能性中疲於奔命地寻找可行解,而顾南舟口中的单砖,却是用自身的几何法则,直接將所有错误路径在萌芽状態就切断。
前面的討论还在继续。
顾南舟开始梳理歷史脉络。
从王氏砖(wang tiles)的不可判定性,讲到替代铺砌(substitution tilings),再讲到如何利用元砖(metatile)构建更大的层级结构。
讲到深处,黑板上已经推满了替代图、局部补丁、角度约束和几行简单的组合计数。
“为什么一块砖这个看似简单的条件,会让问题变得如此棘手?”
顾南舟指著黑板上的复杂推导。
“因为没有了第二种形状来做缓衝和制约,你无法轻易地切断周期性。单独的一块砖,太容易首尾相连形成平移对称了。”
一个研二的学生苦笑著插话:“老师,这听起来就像是要求我们打造一把钥匙,这把钥匙既能打开世界上所有的门,又偏偏在物理法则上註定了它不能被任何门复製,这要求太反直觉了。”
顾南舟难得地笑了一下。
“比喻得不错,它最艰深的地方就在於,你要把庞大的,甚至趋於无限的全局信息,毫无遗漏地摺叠进一个微小的局部几何边界里。”
江临盯著笔记本上那句,把全局信息藏进局部几何里。
这与他之前推演的search_sort_network本质上是同一件事。
在量化的底层系统里,他是试图把全局的排序正確性隱藏进一串局部的compare-swap操作约束中。
在铺砌问题里,则是要把无限平面的非周期性隱藏进一块砖的几道凹凸边界里。
底层逻辑是相通的。
一个多小时的读书班转眼结束。
顾南舟宣布散会,但没有人立刻离开。
学术討论的余温还在。
几个学生围在长桌前,研究顾南舟带来的一些高清列印图纸。
有人在爭论准晶体衍射图谱的对称性,有人在討论十次对称轴在实际材料中的稳定性。
刚才那个提问的研二学生拿了支铅笔,在草稿纸上隨手画著各种扭曲的多边形,试图凑出一个不规则的形状。
“要是真有这么一块符合条件的单砖,它到底会长成什么鬼样子?”
他一边画一边摇头,语气轻鬆,全当是一个消遣的数学玩笑。
而江临呢?
他当然不是第一次见到这种问题。
mps的状態空间爆炸,逼著他反覆想一件事。
怎样把看似无穷的路径,压成有限几类状態。
阿里预赛里的磁性几何魔方,也曾逼他把纷乱的空间构型压成连接图与上界。
拆盲盒那道题,则让他再一次確认,只要对称性足够强,状態就不该按具体对象命名,而该按还缺几种这样的等价类命名。
他脑海中,mps v0.2的那三个问题。
哪些状態可以合併?
哪些死路可以提前砍掉?
砍掉之后,怎么证明自己没有误杀真正的解?
顾南舟刚才讲的 metatile,像是突然给这三个问题换了一套几何外壳。
转移,不再是 compare-swap,而是一块砖贴上另一块砖。
死路,也不再是跑不通的候选程序,而是一个无法填补的角缺口。
他原本为 mps 画过许多状態转移草图。
有些草图,为了看清边界,已经被他画成了几何拼接。
现在,这些草图忽然有了新的名字。
metatile。
substitution。
forced hierarchy。
所以他第一眼想的不是图案好不好看。
而是三个问题。
能不能生成一整张平面?
能不能证明所有合法拼法都被迫归入同一套层级?
如果层级成立,能不能反证周期?
一念及此,江临的手腕开始移动。
笔尖落在纸上,没有迟疑。
他先画了一个极小的风箏形。
那些边都落在同一套辅助网格上,几类角度反覆出现,刚好能让凹口和凸边形成有限种邻接关係。
接著,他以一种特定的拓扑结构,將八个这样的小风箏形拼接在一起。
纸面上顿时出现了一个十三边形。
它並不规整。
边缘充满了突兀的內凹和外凸,像是一顶被人粗暴压扁,又用力拧了一把的怪异帽子。
轮廓没有任何常规几何图形的对称美,透著一种冷硬的机械感。
旁边那个画图的博士生眼角余光扫到江临的本子,停下笔,饶有兴致地探过头来。
“同学,你这画的是什么,坏掉的风箏?”
他笑了笑,没有恶意,只是觉得这个形状古怪得有些滑稽。
江临没有抬头,也没有回答。
他的手腕继续移动,在这块怪帽子旁边,紧贴著它的凹槽,画出了第二块一模一样的砖,只是进行了旋转。
严丝合缝。
接著是第三块,第四块。
这些形状怪异的砖块,以一种看似极度彆扭,在视觉上让人產生错位感的方式交错在一起。
但它们的边缘却咬合得如同精密的工业齿轮,没有留下一丝缝隙。
解答了学生疑问的顾南舟,正要离开,从江临旁边经过时,刚好看到了这一幕。
不由得停了下来。
低头看著那几块咬合在一起的十三边形,沉默了几秒钟,问道:“这位同学,这是你自己画的?”
“是。”
顾南舟若有所思地问道:“这块形状,能铺满?”
“能。”
一旁的博士生听到江临的肯定回答,立刻来了精神,放下手里的草稿纸转过身来。
“能铺满不稀奇,很多形状只要能凑出一个周期基本胞,就可以周期铺。”
附近几个学生也注意到了这边,还以为江临只是隨口放了个大话。
能不能周期铺,哪是看几块手绘图就能断言的。
顾南舟没有將这位博士生的话听进去,他正盯著纸上那几块拼接的图形出神。
那些凹角、凸角和几条斜边的组合关係,正在顾南舟脑海中快速重组。
半晌,他拉开旁边的一把椅子坐下,看著江临,沉吟道:“要不要试著证明一下看看?”
江临点点头。
因为这不是他刚才在教室里灵光一闪的涂鸦。
在过去几天里,他为了mpsv0.2反覆画过很多局部状態图。
有些是程序里的状態。
有些被他顺手画成了平面上的边界。
他原本只是想找一种可视化方式,帮助自己理解哪些路会死,哪些路会被迫归入同一类。
直到顾南舟讲到metatile,他才意识到,那些被自己当成辅助图的边界草稿,本身就可以变成一个几何问题。
他只是缺乏一套正统的数学语言去包装它。
而今天下午,顾南舟的读书班,刚好把这套语言递到了他手里。
substitution(替代规则)。
forced hierarchy(强迫层级)。
metatile(元砖)。
这些词汇,如同坚固的模具,將他那些原本只是用来辅助理解死路、归类、继承的边界草图,压入了一个能被当代离散几何学界审视的框架內。
“第一步,我不会直接证明非周期,而是先证明它能够铺满整个平面。”
江临说话的时候,在纸的左侧,画了几个单砖,將它们拼合在一起,形成了一个更大的,轮廓依然带有特定凹凸特徵的块体。
然后在这个块体旁边標上了一个字母:h(hex)。
紧接著,他利用不同的拼接方式,又画出了另外三种由单砖组成的复合块体,分別標上:t(turtle)、p(propeller)、f(fang)。
它们无一例外,边缘都带有极具特徵的几何齿。
那个博士生眉头微微皱起,低声喃喃:“这是在造超大號的砖?”
顾南舟抬起手,示意他安静。
江临没有理会外界的声音,继续在白纸上推演。
“这四种块体,属於第一层级的metatile。”
他在h块体的旁边,开始画下一层级的替代图(substitution map)。
“根据这块单砖的几何特性,h块体本身,可以被更小的h、t、p、f 按照一种不可更改的拓扑结构拼凑而成。”
“t也可以。”
“p和f也一样。”
笔尖在纸上快速游走,每一条边每一个转角的比例都异常精准。
“每一种更高层级的块体,都能由上一层的这四类metatile严密组合出来。”
画到第三层级替代的时候,纸面上的结构已经变得相当复杂,但无论內部如何交错,整体的边界依然保持著最初设定的拓扑特徵。
这一刻没有人再隨口质疑。
因为从这一刻开始,问题已经从这是不是涂鸦,变成了这张局部邻域表有没有漏项。
刚才那个博士生更是已经处於屏气凝神状態,死死盯著那些咬合的缝隙。
“这是一套严格的substitution rule(替代规则)?”顾南舟小声问道。
“对。”江临停下笔,“只要这套替代规则可以在数学上无限叠代,就意味著这个平面可以被尺度越来越大,直至趋於无穷的metatile完全覆盖。”
他在纸的边缘写下:
level 0: tile
level 1: h/t/p/f
level 2: substituted h/t/p/f
...
level n→∞: tiles the plane
“能铺满,第一步闭合。”江临淡淡地说。
“你现在只证明了,依靠这套替代规则,这块砖有一种非周期味道很强的铺法。”顾南舟盯著江临的眼睛,“我在课上说过,这远远不够。”
江临点头:“我知道。”
“所以你要证明,不是你在上帝视角选择了这个层级拼法,而是这块砖本身的几何边界,被迫且只能长成这个层级。”
“所以,第二步不是铺。”
江临將画满替代规则的a4纸往旁边推了推,又抽出一张新纸。
在纸的中央单独画出那块十三边形单砖。
“是强迫(forcing)。”
他用笔尖圈出单砖边界上的三个关键凹角,接著,又圈出对应的几个凸角。
“我们不看全局,只看局部。在严密铺砌的约束下,平面不允许留下任何缝隙,也不允许任何重叠。这意味著,单砖上的每一个凹角,都面临著生死存亡的选择,它必须被另一块砖的某一种凸角咬住。”
他在凹角周围,画出了第一种邻接砖的拼法。
“第一种补法,合法。”
接著是第二种。
“第二种,合法。”
第三种。
“第三种,合法。”
然后,他画出了第四种拼法。
这块砖在凹角处完美贴合,但在另一端,却突兀地伸出了一截。
江临毫不犹豫地在它旁边打了一个巨大的叉。
“这类局部填法,表面上看在一个顶点处接上了,但只要再往外延伸一圈,它的另一端就会形成一个30°的死角。而我们的单砖系统里,不存在能填补30°缺口的凸起,这是一条死路。”
博士生忍不住插嘴:“等一下,你怎么能確定局部邻域只有这几种拼接可能?平面的组合是指数级爆炸的。”