“It makes me a little sorry we (as a species) did not settle on origami as a computing platform. It would be great to see computers folding and unfolding themselves. It would likely be a little slower I suppose.”
按年被提到
20232025 · 3 次2026
Flat origami is Turing Complete
平折纸是图灵完备的
Thomas C. Hull, Inna Zakharevich · 2023
用带可选折痕的折纸图案模拟 Rule 110,证明平折纸图灵完备
被提及 · 6 人首次 2023-09-21 · 最近 2025-04-22
6不同的人
4活跃月份
6讨论串
4被引(OpenAlex)
论文把平折纸形式化为带层序的分段等距映射,并证明把它当作计算装置时是图灵完备的,更准确地说是 P 完全的。证明方法是构造带「可选折痕」(是否折叠取决于其他折痕或输入所施加的约束)的折痕图案,用来模拟被 Matthew Cook 在 2004 年证明图灵完备的一维元胞自动机 Rule 110。
HN 为什么提它
输入里没有评论摘录,具体语境无法确定;它被多人在不同月份提起,大概因为「折纸竟然图灵完备」这个结论本身就很有趣。
其他难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1图灵完备(Turing completeness)
2元胞自动机 Rule 110
3计算复杂度(P 完全、NP 完全)
4折纸数学与折痕图案(crease pattern)
HN 书评
没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)讨论串评论tocs3 · 2025-04
讨论串评论NooneAtAll3 · 2025-04
“> we prove that flat origami, when viewed as a computational device, is Turing complete, or more specifically P-complete...aren't those mutually exclusive? I feel a mix of "those are obviously different complexity levels" and "is it like C pre-processor turing-completeness situation?"”
讨论串评论gitroom · 2025-04
“Honestly wild how you can get Turing completeness outta folding paper, never thought I'd read that today.”
被提交为 story · 6 次
- Flat origami is Turing Complete ↗082349872349872 · 2023-09-21 · 2 分
- Flat origami is Turing Complete ↗RafelMri · 2024-01-31 · 2 分
- Flat origami is Turing Complete ↗LearningToWalk · 2024-02-12 · 4 分
- Flat origami is Turing complete (2023) ↗fanf2 · 2025-04-14 · 4 分
- Flat origami is Turing Complete (2023) ↗thunderbong · 2025-04-16 · 2 分
- Flat origami is Turing complete (2023) ↗PaulHoule · 2025-04-22 · 40 分