How to Build an Origami Computer

https://www.quantamagazine.org/how-to-build-an-origami-computer-20240130/

by digital55 • 2 years ago

63 15 2 years ago

kian2• 2 years ago

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.

kian2• 2 years ago

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.

grow2grow• 2 years ago

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

andrewflnr3• 2 years ago

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.

dekhn2• 2 years ago

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.

dekhn2• 2 years ago

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.

photonthug• 2 years ago

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/

jksk61• 2 years ago

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.

andrewflnr3• 2 years ago

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.

charcircuit• 2 years ago

Come up with something complex and give it finite memory.

d--b• 2 years ago

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.

fuzzythinker• 2 years ago

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

elliotwagner• 2 years ago

Very neat, fuzzythinker

How to Build an Origami Computer

Related Stories