How to Build an Origami Computer | Hacker News Reader

How to Build an Origami Computer

quantamagazine.org

63 pointsdigital5515 comments

Thought this result was already established so maybe it's a new angle or simpler proofs? Obligatory Erik demaine linkage for those interested in more tho: https://ocw.mit.edu/courses/6-849-geometric-folding-algorith... https://erikdemaine.org/

now the question is: what is the most complex* object that it is not turing complete?

* let's say you have n distinct rules acting against a set S, the complexity is n.

p.s. probably something trivial exists such that you can take n as large as we wish to, so probably my definitions are not interesting.

I think complexity is entirely the wrong question to ask regarding Turing completeness. It's about the kind of rules, not how many.

That said, maybe the cheekiest answer is an actual computer: fantastically complex, but technically TC requires infinite memory.

Come up with something complex and give it finite memory.

I’ve thought origami was the way to prove p!=np for a while. Just waited for Erik Demaine to prove it though cause he’s like a billion times smarter than I am.

I built one that simulates folds -- https://foldmation.com

Very neat, fuzzythinker

So, then, protein folding is likely also possible to make Turing complete, no?

Protein folding is Turing complete because it can simulate a Turing machine by folding itself into a homo sapien, taking computation theory in college, and stepping through a Turing machine with a pen and paper for homework.

I love this response. On a slightly smaller scale, there are also ideas of protein interaction-network computational 'circuitry' -- I think that showing that folding can also compute is a nice addendum to this.

Thank you for this excellent example, which I'll be using when defending my unpopular opinion that Occam's razor is nonsense.

If they are, it will be for completely unrelated reasons. Protein folding has very little in common with paper folding beyond the name. In particular, proteins are basically 1-dimensional, whereas paper folding is inseparable from the 2d nature of paper.

protein are 1-dimensional only if you throw away large numbers of degrees of freedom, and every detail of their folding is determined by their three-dimensionality.

That's equally (almost vacuously) true of origami, but the inherent topology of the building blocks still has a huge effect on what those degrees of freedom actually are. Do you think they're similar between a peptide chain and a sheet of paper? If no, then what are you actually arguing?

proteins themselves are turing complete; the folding is not really the interesting bit. just like there is a turing tarpit, trying to do anything reliable with protein folding (the process) is not likely to be effective. Instead, merely use existing functions provided by evolution to manage a DNA tape. You don't even need proteins; you can do it with just RNA and DNA. If you're really clever, with just RNA, and if you're super clever, just DNA.

Reply on news.ycombinator.com