3 ms·
The reduction in the article boils down to origami crease patterns simulating rule 110 simulating a cyclic tag system simulating a clockwise Turing machine simu
by yorwba 2y ago
The reduction in the article boils down to origami crease patterns simulating rule 110 simulating a cyclic tag system simulating a clockwise Turing machine simulating an arbitrary Turing machine (and specific Turing machines simulating the lambda calculus are known).
Do you think there is an "obvious" way to simulate the lambda calculus using origami crease patterns more directly? For example, a cyclic tag system or even rule 110 configuration simulating the lambda calculus without indirection through Turing machines.
- entaloneralie 2y agoIf I may chip in, I wouldn't call it obvious or straight-forward, but multiset rewriting[1] can be implemented in terms of multiplication alone(like in Fractran), and multiplication can be implemented in origami[2], so there might be something there. [1] https://wiki.xxiivv.com/site/pocket_rewriting https://wiki.xxiivv.com/site/pocket_rewriting [2] https://wiki.xxiivv.com/site/paper_product.html https://wiki.xxiivv.com/site/paper_product.html