2020 年 4 月 8 日,约翰·霍顿·康威出现新冠症状,4 月 11 日因该疾病去世。作者缅怀康威,介绍其在数学领域的成就,如《生命游戏》《数字与游戏》《超现实数》等,重点阐述了 FRACTRAN 编程语言。
FRACTRAN 相关内容:
- 编程示例:FRACTRAN 程序是正分数的有序列表和初始正整数输入 n,运行时按规则更新 n,直到无分数能使 n 乘后为整数则停止。例如计算斐波那契数的程序
17/65
,133/34
等,计算fib(7)
时,经过一系列分数乘法和判断后最终停止,结果为 13,此程序包含程序本身、初始 n 值(可通过特定函数计算)、从 n 值到结果的转换(如log2
函数)。 - 用 JavaScript 实现:编写 FRACTRAN 解释器很简单,用 JavaScript 实现计算斐波那契数的函数时要注意处理大整数,需自己实现
log2
和pow
函数。
- 编程示例:FRACTRAN 程序是正分数的有序列表和初始正整数输入 n,运行时按规则更新 n,直到无分数能使 n 乘后为整数则停止。例如计算斐波那契数的程序
马文·明斯基的机器:
- 明斯基机介绍:明斯基机是计算通用的理想化机器,属于寄存器机家族,有有限个状态和磁带,磁带可无限延伸,每个磁带有一个磁带头,能根据指令移动磁带头和改变状态,与图灵机类似但有差异,如可同时移动多个磁带头、不能在磁带上写字等。
- 创建明斯基机:用特定语法描述明斯基机的程序,包括状态、规则(包含动作子句和守卫子句)等,通过扫描规则、检查守卫子句、执行动作子句等来运行机器,还介绍了加法和乘法的明斯基机示例及实现过程。
- 神奇的明斯基机:通过在乘法的明斯基机中添加额外磁带模拟其他状态,得到只需一个状态但更多磁带的神奇乘法机,还给出了从任意宏伟明斯基机推导出神奇明斯基机的算法。
哥德尔编码与精湛的明斯基机:
- 哥德尔编码:是为形式语言中的符号和语句分配唯一自然数的方案,这里用素因子分解来编码有限个有限数,可用于编码明斯基机的状态,将动作和守卫子句也用素因子分解表示,从而将整个明斯基机状态编码为一个自然数。
- 实现单数量明斯基机:给出了将宏伟明斯基机转换为精湛明斯基机的函数
toMasterful
,以及评估单数量明斯基机的函数evaluate
,并通过示例展示其功能。
等价性探讨:
- 表面上看,FRACTRAN 与神奇明斯基机不同,但本质上它们是相同的算法,只是实现方式不同,神奇明斯基机是 FRACTRAN 解释器的一种形式。通用明斯基机 U 可模拟任何明斯基机,而每个明斯基机都有等价的 FRACTRAN 程序,如康威的 POLYGAME 就是通用 FRACTRAN 程序。
- 科拉茨猜想:FRACTRAN 程序可用于测试科拉茨猜想,通过设置 n 为 2ˣ等方式,程序在达到 2¹时停止,若存在反例则程序会一直运行。FRACTRAN 与科拉茨函数和游戏相关,Rice 定理表明 FRACTRAN 游戏是不可判定的,这对理解科拉茨猜想有重要意义。
- 附录:包括康威的“FRACTRAN:一种荒谬的逻辑语言”讲座视频、诺曼·怀尔德伯格关于科拉茨猜想的讲座视频、维克拉姆·拉马纳坦关于 FRACTRAN 的文章等。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。