2020年4月8日，约翰·霍顿·康威出现冠状病毒症状。2020年4月11日，他死于这种疾病。1 2 3 4。
像很多人一样，我哀悼康威的逝世，但我也颂扬他的一生。我赞颂他的成就，我赞颂他的好奇心，我赞颂他使重要的数学主题引人入胜和有趣的技巧。
这项技能的一个最好的例子是本文的主题编程语言FRACTRAN。
康威从早年就触动了我自己的生活。正如我在八皇后问题…中所描述的那样。以及拉甘瓦尔德意想不到的怀旧之情：
有一次，我母亲送我去了一个天才儿童日营，它的组织方式就像一所大学。“学生”自选选修课，我选了一门叫“乌敦尼特”的选修课。结果是半天的拼图和游戏练习，我被吸引住了。
我还能在哪里学到在超级立方体里玩井字游戏？还是关于说谎者和说真话的人？或者，碰巧，关于马丁·加德纳？我怀疑所有的材料都是从他收集的专栏中拿出来的，这很适合我。
我们在“胡敦尼特”中谈到的其中一件事是康威的生活游戏。我记得在那里听说过它，但我也不记得经常玩它。当时发生了很多事情，完全有可能是因为我太忙着爱上雷蒙德·斯穆利安，以至于没有给约翰·康威留下好奇心。5 6 7。
在我的一生中，我又几次重新发现了康威的“人生游戏”(Game Of Life)。我们在大学里谈过。几年后，我读了威廉·庞德斯通(William Poundstone)的“递归的宇宙：宇宙的复杂性和科学知识的极限”，它真的让我大吃一惊：
一路上，我学到了一些博弈论的知识。我喜欢各种各样的游戏，我想我在图书馆里发现了“战略游戏：理论与应用”，并把它拿了起来，想着它会对我的五子棋有所帮助。
这就把我带到了康威的“论数字和游戏”，并通过平行的路径，到达了超现实的数字。就像“生活的游戏”(Game Of Life)一样，超现实的数字不断出人意料地出现，重新点燃了我对我们如何表示数据、提供或阻碍处理这些数据的方式的兴趣。
1987年，康威为1984年和1985年在新泽西州莫里斯敦和1986年夏天在帕洛阿尔托举办的关于通信和计算问题的特别研讨会贡献了FRACTRAN：一种简单的通用算术编程语言。加利福尼亚。FRACTRAN本身在该领域并不是一个重要的公开问题，但正如已发表论文的编辑所指出的那样：
也许所有贡献中最有趣的是康威关于FRACTRAN的迷人的文章，这是一个奇怪的数字集合，当以简单的方式操作时，可以产生所有可能的计算。我们从他的文章开始。
--Thomas M.Cover&；B.Gotinath，“通信与计算中的公开问题”10。
正如维基百科所指出的，FRACTRAN程序是由正分数和初始正整数输入n组成的有序列表。该程序通过如下方式更新整数n来运行：
对于列表中nf为整数的第一个分数f，请将n替换为nf。
重复此规则，直到列表中没有一个分数在乘以n时产生整数，然后停止。
例如，这是一个用于计算任何斐波纳契数的FRACTRAN程序：17/65、133/34、17/19、23/17、2233/69、23/29、31/23、74/341、31/37、41/31、129/287、41/43、13/41、1/13、1/3。11。
所有FRACTRAN程序也都以n的初始值开始，该值有时是常量，有时由用户提供。当它由用户提供时，有时需要准备n以使其可用。
在这个程序的例子中，为了计算某个x值的fib(X)，我们计算n=78*5^(x-1)。
让我们使用这个程序来计算fib(7)。我们从n=78*5^(7-1)开始，即1,218,750。我们将跟随一段时间来感受一下会发生什么：
计划中的第一个分数是17/65。1,218,750乘以17/65等于318,750，因此我们将1,218,750替换为318,750，然后重新开始。
计划中的第一个分数是17/65。318,750除以65会剩下余数，所以我们继续前进。
节目的下一个分数是133/34。318,750乘以133/34等于1,246,875，因此我们将318,750替换为1,246,875，然后重新开始。
节目的下一个分数是13/41。24576除以41会剩下余数，所以我们继续前进。
程序中的下一个分数是1/13。24,576除以13会留下余数，所以我们继续。
程序中的下一个分数是1/3。24,576乘以1/3是8,192，所以我们用8,192替换24,576，然后重新开始。
8,192是一个重要的数字，因为没有一个除数可以均匀地除以8,192。所以我们看到。
计划中的第一个分数是17/65。8192除以65会剩下余数，所以我们继续前进。
节目的下一个分数是133/34。8,192除以34剩下的余数，所以我们继续前进。
程序中的下一个分数是17/19。8,192除以19剩下的余数，所以我们继续。
节目的下一个分数是13/41。8192除以41会剩下余数，所以我们继续前进。
程序中的下一个分数是1/13。8,192除以13后剩下的是余数，所以我们继续。
程序中的下一个分数是1/3.8,192除以3剩下的是余数，所以我们继续。程序中没有一个去中心化程序平均分配到8,192个，所以程序暂停。
所有FRACTRAN程序都会为n生成一系列值，并且必须从这些值中提取我们想要的结果。对于我们的Fibonacci程序，这些值以1,218,750、318,750、1,246,875和1,115,625开始，然后以221,184、73,728、24,576和8,192结束。13个。
在斐波纳契数列中，我们想要的结果是n的最后一个值的log2。n的最后一个值是8,192，log2(8,192)是13，这就是我们想要的答案。第7个斐波纳契数是13。
程序本身，一个有限的分数列表。本节目名单为17/65、133/34、17/19、23/17、2233/69、23/29、31/23、74/341、31/37、41/31、129/287、41/43、13/41、1/13和1/3。
初始值n。它可以是常量，可以是用户提供的值，也可以是用户定义的值的转换。该程序的转换可以用JavaScript表示为n=>；78*Math.pow(5，n-1)。
从n的值到我们想要的结果的转换，按照我们想要的方式编码。在我们的示例中，它类似于VALUES=>；Math.log2(last(Values))。
编写FRACTRAN解释器非常容易。让我们从编写一个JavaScript Fibonacci函数开始，该函数使用我们的FRACTRAN程序来实现。我们需要注意的主要问题是，n的值可能会变得非常非常大，因此我们需要使用大整数，也就是“BigInts”14。
处理大整数的一个后果是，我们依赖于数字的许多东西不再有效。例如，Math.log2(8192)=>；13，但math.log2(8192n)=>；TypeError：无法将BigInt值转换为数字。我们必须编写我们自己的log2函数。
Math.pow也是如此，我们将不得不写我们自己的。如果您愿意，可以随意使用这些实现：
//任何足够复杂的循环函数，包含特定的、//非正式指定的、充满错误的、缓慢实现的//一半线性递归常量log2=(N)=>；{let result=0n；while(True){//退化条件if(n==1n)Break；//(n%2n==1n)RETURN；IF(n<；1n)RETURN；//分治征服++RESULT；//(n%2n==1n)RETURN；IF(n<；1n)RETURN；//分治++RESULT；n=n/2n；}返回结果；}常量幂=(基，指数)=>；{if(指数<；0n)返回；设结果=1n；而(指数-->；0n)结果=结果*基；返回结果；}。
现在继续编写您自己的实现。在您编写完自己的代码之前，请忽略下面的代码。
//使用log2和上面的幂来制定种子并解密结果const fib=(X)=>；{const program=('；17/65,133/34，17/19，23/17,2233/69，23/29，31/23，74/341，'；+'；31/37，41/31,129/287，41/43，13/41，1/13，1/3'；)。拆分(/(？：\s*，|\s)\s*/)。映射(f=>；f.。拆分('；/'；)。map(n=>；BigInt(N)；设n=78n*power(5 n，BigInt(X)-1 n)；Program_start：while(True){for(const[分子，分母]，程序){if(n%denominator=0n){n=(n*分子)/分母；Continue Program_start；}}Break；}return log2(N)；}；FIB(7)//=>；13。
这太酷了。FRACTRAN程序非常小，而且简单得离谱：它只是分数。中央FRACTRAN解释器也非常小：它实际上是WHILE循环中的FOR循环，如果JavaScript支持GOTO，则可以避免WHILE循环(以及BREAK语句)。15个。
尽管FRACTRAN表面上看起来很优雅，但乍一看，它似乎是高深莫测的。它是不是一种既不好读也不好写的语言？或者，有没有一种方法可以通过编写分数列表来疯狂地编写程序？
要回答这个问题，我们必须首先考虑另一位伟大思想家马文·明斯基(Marvin Minsky)的作品。
1987年9月，斯图尔特·布兰德在麻省理工学院出版了“媒体实验室：发明未来”。说这本书影响了我是不公平的。就像许多商业和技术圣徒传记一样，它对麻省理工学院和导演尼古拉斯·尼葛洛庞帝(Nicholas Negroponte)试图做的事情赞叹不已。
这也很有启发性：布兰德详细描述了媒体实验室是如何由其企业赞助商资助的，以及资助模式是如何推动研究的。他们的座右铭是，“不演示就死”，这意味着这些钱流向了那些不仅能让同龄人惊叹的人，还能提供舞台魔力，让他们的企业赞助商打开钱包。
当时我在科技企业销售部工作，我敏锐地理解到，虽然没有牛排很难卖出SIZE，但当你有非常好的牛排，但没有SIZE的时候，同样不太可能获得销售。16个。
媒体实验室提到的其中一个人物是马文·明斯基(Marvin Minsky)。明斯基被认为是人工智能领域的巨人，人工智能是当时的郁金香狂热。历史将表明，随着这本书的出版，人工智能资金开始了另一次周期性崩溃，但当我读这本书时，杂志和书架在令人窒息的散文和乌托邦愿景的重压下呻吟。
1985年，明斯基出版了“心灵学会”，我在媒体实验室读到有关明斯基的文章后买下了这本书。1994年，一家名为旅行者(Voyager)的公司出版了“心灵社会”(Society Of Mind)的CD-ROM版，我用苹果的一款比较古怪的产品--从菲利普斯那里借来的CD-ROM阅读器和音频-CD播放机--“玩”了这个版本，并打上了PowerCD的牌子。
CD-ROM的特色之一是对明斯基的办公室进行互动参观。我仍然清楚地记得他关于他挂在墙上的镜子的讨论，他提到费曼写了一整本书，致力于解释一件事：光实际上是如何从镜子上反射出来的，在这本书中，他解释了为什么所有非专业人士相信的关于光和反射的东西实际上都是错误的。
与费曼和康威一样，明斯基也有解释具有挑战性的想法的天赋。他也像费曼和康威一样，为人类知识的进步做出了巨大贡献。他的研究领域之一是可计算性，具体地说，就是研究一类理想化的计算机器，这些机器现在被命名为明斯基机器(Minsky Machines)，以纪念他的名字。17 18。
明斯基机器是一种理想化的机器，已经被证明是计算通用的。明斯基机器是称为寄存器机器的理想化机器家族的一部分。
就像寄存器机器和图灵机一样，明斯基机器形成了一个小家族，它们之间在想象的方式上略有不同，但在计算上都是等价的。我们将讨论明斯基机器的一种特别简单的形式，我们称之为“宏伟的”明斯基机器。19个
就像图灵机一样，宏伟的明斯基机器也有有限的状态。然而，Magnificent Minsky机器没有单一的磁带在一个或两个方向上延伸到无限远，而是有有限数量的磁带，每个磁带只在一个方向上延伸到无穷大。
就像图灵机一样，一台宏伟的明斯基机器为每一盘磁带都有一个磁头，根据它的指令，可以移动它的磁头并改变到不同的状态。与图灵机不同的是，一台宏伟的明斯基机器可以将其磁头在任意方向上移动任意限量。我们称这些方向为向前(“远离开始”)和向后(“朝向开始”)。
当图灵机与其磁头下面的特定符号相匹配时，它可以写入符号，也可以将磁头向任意方向移动一个正方形。
与图灵机不同，一台宏伟的明斯基机器不能在它的磁带上写任何东西，因此与它的磁头下面的任何东西都不匹配。它能做的就是测试是否有可能执行一个动作。既然总是可以前进的，我们唯一关心的就是后退有没有可能。
与图灵机不同的是，一台宏伟的明斯基机器可以同时移动零个或多个磁头。因此，它的测试可以检查一个或多个磁头是否可以向后移动。
举一个字面上的例子，如果磁头在开头，就不可能后退。如果磁头向前移动n个方块，则可以向后移动<；=n个方块，但不能移动所有>；n个方块。
这些设计选择的最终效果是，Magnificent Minsky Machine可以存储任意数量的状态，就像图灵机一样，但它通过使每个磁头与其磁带的开头保持任意距离来存储该状态。20个。
让我们使用宏伟的明斯基机器编写一个程序。现在我们已经大致了解了这些机器是如何运行的，下面是我们将如何指定每台Magnificent Minsky机器，即我们应该如何编写其“程序”：
我们的机器将有有限数量的状态，用连续的正整数表示，即1，2，3，…。
每条规则都将表示为“如果这样做，如果那样做”。因此，它们将有两个条款：一个行动条款和一个守卫条款。
ACTION子句应由一组向前移动的磁头和每个磁头表示移动多少方块的正整数组成。我们将把它们记为(磁带标识符^要向前移动的正方形)的元组。ACTION子句是这样的元组的无序集合，同一规则中没有两个元组共享相同的磁带头。ACTION子句还将包括一个正整数，指示要进入的下一个状态。
保护条款应由一组向后移动的磁头和一个正整数组成，该正整数表示向开始移动的方块数。与ACTION子句一样，同一规则中的两个保护子句不能共享同一磁头。
由于同一规则中的两个子句不能共享同一个磁带头，因此没有一条规则可以既测试保护子句中的磁带头，又同时移动操作子句中的磁带头。
我们的Magnificent Minsky机器是通过将磁头放置在特定位置进行初始化的，因此，除了列出其中的状态和规则外，Magnificent Minsky机器的说明还将包括设置磁头初始位置的说明。
当我们希望运行Magnificent Minsky机器时，我们将其启动为状态1。我们通过按顺序扫描当前状态内的规则来操作我们的机器。
对于每个规则，我们检查其保护条款。如果可以将保护子句中的所有磁头移向开头，则规则“触发”，我们按照保护子句所指定的那样将磁头移向开头。然后，我们参考操作条款，并将列出的所有磁头从末尾移开列出的数量。最后，当规则触发时，如果它列出了下一个状态，我们将更改到该状态，并返回到按顺序扫描当前状态中的规则。
如果任何规则的保护条款不能执行磁头朝向开头的所有必需的移动，则该规则失败，并且磁头不会受到干扰。然后，我们继续尝试该州列表中的下一个规则，然后再尝试下一个规则，依此类推。如果当前状态下的所有规则都失败，计算机将暂停。由此可以得出结论，如果机器在没有任何规则的情况下进入一种状态，它就必须停止。
如果机器试图转换到未定义的状态，它也会停止。因此，显式转换到状态0是显式停止机器的格式良好的方式。
现在我们准备好讨论Magnificent Minsky机器的一个简单符号，并尝试一个。
考虑一台伟大的明斯基机器，它将把两个数字相加。我们只需要一个州，有两条规则。我们的符号将会很简单。在每个州，都有一个逗号分隔的规则列表。因为我们的第一台机器中只有一个状态，所以我们现在只讨论如何写下规则。
我们州将有一个逗号分隔的规则列表，即规则1、规则2。空格并不重要，因此我们还可以编写规则1、规则2，甚至：
(与大多数编程语言一样，我们如何使用空格安排程序是为了便于人类阅读而组织布局的问题。)。
每条规则都有一个操作子句和一个守卫子句，用/分隔，例如：
/显然类似于除法的表示法，但在Magnificent Minsky Machine中，它实际上并不意味着“除法”，它只是将每个规则中的操作子句与守卫子句分开。
动作子句和保护子句都有完全相同的符号：形式为(t^s)的一个或多个元组，其中t标识磁头，s标识要移动的方块数量。^字符在一些编程语言中表示幂运算，但在Magnificent Minsky Machine中，它只是一种分隔两个数字的方式。
(1^1)(4^1)是action子句，它有两个元组：(1^1)表示将磁头1移动1平方，(4^1)表示将磁头4移动1平方。
(3^1)是保护条款，它说要将磁头3移动一个正方形。
在Magnificent Minsky机器中，动作子句总是将磁头向前移动，而保护子句总是将磁头向后移动，所以我们不需要让我们的子句使用+或-或指向不同方向的箭头，只要知道/左边的子句是动作子句并将磁头向前移动就足够了，而/右边的子句是保护子句，并且向后移动磁头就足够了。
现在来看我们的第一台机器：我们的机器只有一种状态1，它有两个规则：
我们的程序将两个正数相加，我们称之为a和b。它有三盘磁带，1、2和3。为了设置机器，我们将磁头1放在磁带的开头，将磁头2a正方形放在前面，将磁头3b放在正方形前面。当机器停止时，磁头1将是a+b正方形向前，而磁头2和3将在开始处。
我们可以用它将数字2+2相加，看看是否会得出4。我们将如何以图形方式显示磁头的位置：21。
这表明磁头1在开始处，而磁头2和3在前面两个正方形处，即开始处
..