算法与理论计算机2024mgs.spatial-computing.org
作为拓扑空间的数据结构 (2002)
Data structures as topological spaces (2002)
专业 · 约 45 分钟读完前置知识：拓扑学基础、数据结构、并发/反应式计算
导读
这篇 2002 年的论文尝试把数据结构视为拓扑空间，用拓扑邻域和变换来描述结构及其变化。评论者将其理解为一种面向动态结构/并发计算的建模方式，并举例说可用变换原语表达 Conway 生命游戏规则；具体形式化细节仍需读原文。
HN 关注点：“拓扑空间”视角与常见图结构建模有何本质区别，以及它和化学反应、并发计算、同伦类型论等概念的联系。
HN 评论精选
这几条评论里：质疑 1 补充 3
补充指向更相关的论文 PDF，并把论文动机解读为拓扑邻域中的反应模型，同时指出项目已不维护，还举例说明可用变换原语实现生命游戏。
我觉得下面这个 PDF 更能表达他们想做的事。据我理解，他们试图建模化学反应等过程：溶液中有若干“东西”，如果处在同一拓扑邻域就会结合；大意是不必所有东西都彼此紧挨，因为溶液静置后最终会发生反应。挺有意思，但网站显示项目不活跃，至少 2010 年后似乎没有公开文档。比如可用 trans 变换原语实现 Conway 生命游戏：把出生规则定义为一个空细胞加三个活细胞的模式，变换后空细胞变活、活细胞不变；死亡规则类似。这里的邻居被定义为物理相邻，但既然是拓扑，邻居不必是物理邻近……不确定在哪定义，可能在 collection 里。然后对初始状态集合运行变换即可。
Verdex查看英文原文
It feels like the following PDF better expresses what they're trying to accomplish. http://mgs.spatial-computing.org/PUBLICATIONS/lami-RR72--computational-models-for-dynamical-structure.pdf As far as I can tell, they're trying to model things like chemical reactions (and other stuff) where given a bunch of "stuff" in some solution it will combine with other "stuff" if it's in the same topological neighborhood (which I think is basically the idea that ALL of the "stuff" doesn't have to be next to each other b/c if you let a solution just sit there eventually reactions are going to react). It's kind of neat, but their website seems to indicate that it is not being actively supported. Or at the very least they don't seem to have any reason to make publicly available documentation after since around 2010. EDIT: So for example, you could use their "trans" transform primitive to implement conway's game of life by defining the birth rule as a pattern of an empty cell with three alive cells and a transform that results in the empty cell being alive and the alive cells being the same. The death rules in similar fashion. Neighbor here would be defined as being physically next to something (but the point is that because this is about topologies, then neighbor doesn't have to mean physical proximity ... although I'm not sure where that's defined ... in the collection maybe?). And then you just run the transform on a collection with some initial state. EDIT EDIT: Yeah, the notion of neighbor is defined on the collection. This allows you to use the same transform on different collection types and get the appropriate result. ALSO checkout figure 5 in the PDF I linked because it's an incredibly concise description of exactly what they're doing. EDIT EDIT EDIT: This also feels vaguely similar to what the Egison language is doing with their pattern matching. Documentation for Egison feels better at least to me. https://www.egison.org/ However, I don't think that egison allows you to define arbitrary notions of neighbors in a collection like MGS does. But I haven't exactly tried to use it very much.
质疑质疑拓扑空间视角相比图建模是否带来根本性的新东西。
这跟把数据结构看成图有本质区别吗？
misja111查看英文原文
How is this fundamentally different than considering data structures as graphs?
补充联想到同伦类型论，询问两者是否存在关联。
我想知道这篇文章是否与同伦类型论有关，因为它们提出了类似的想法。
anon291查看英文原文
I wonder if this article is related to homotopy type theory at all, since they propose similar ideas.
补充补充联想到 Wolfram 的 ruliad，将其视为并发拓扑计算的一种形式。
Stephen Wolfram 的 ruliad 似乎可以看作某种并发拓扑计算。里面有一些漂亮的图。
hackandthink查看英文原文
Stephen Wolfram's ruliad seems to be some sort of concurrent topological computations. There are some beautiful pictures. https://content.wolfram.com/sites/43/2021/11/1110swimg46.png https://writings.stephenwolfram.com/2021/11/the-concept-of-the-ruliad/
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2024Hacker News 讨论帖170 分 · 46 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选