6 ms·
How to Build an Origami Computer
- kian 3y agoSo, then, protein folding is likely also possible to make Turing complete, no?
- bananabiscuit 3y agoProtein 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.
- grow2grow 3y agoThank you for this excellent example, which I'll be using when defending my unpopular opinion that Occam's razor is nonsense.
- kian 3y agoI 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.
- andrewflnr 3y agoIf 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.
- dekhn 3y agoprotein 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.
- andrewflnr 3y agoThat'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?
- dekhn 3y agoproteins 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.
- d--b 3y agoI’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.
- photonthug 3y agoThought 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-algorithms-linkages-origami-polyhedra-fall-2012/ https://ocw.mit.edu/courses/6-849-geometric-folding-algorith... https://erikdemaine.org/ https://erikdemaine.org/
- jksk61 3y agonow 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.
- andrewflnr 3y agoI 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.
- charcircuit 3y agoCome up with something complex and give it finite memory.
- fuzzythinker 3y agoI built one that simulates folds -- https://foldmation.com https://foldmation.com
- elliotwagner 3y agoVery neat, fuzzythinker