Stuff like this is really fascinating to me because it suggests that computation is an underlying structure in reality. We've found it in sand, gears, marbles, and organisms (and also in that thing between your ears).

We also keep finding ties between computation and mathematics (seriously, read that paper; it's interesting). This might not be as surprising as finding computation in the physical world, but it raises an interesting question. If we use math to reason about reality and computation to help reason about math, how can we build a direct link between reality and computation?

rob05c:

- We also keep finding ties between computation and mathematics

To paraphrase Abelson and Sussman, Computer Science is neither about computers nor a science. Computer Science *is* mathematics. They're different sides of the same coin. Mathematics is declarative; Computer Science is imperative.

- it suggests that computation is an underlying structure in reality.

If by 'computation' you mean the capabilities of a computer (that is, a Turing Machine), we really don't know. It has huge implications if physics and the universe are limited by formal Computability. Likewise, the human mind.

Importantly, computers can't do everything. The classic example is the halting problem. No computer program can determine if any other program will eventually stop. It isn't possible. We've mathematically proven it. But as humans, we can look at a computer program and say "oh, that will halt" or "that will run forever." But can a person do it for *any* program, if only they're smart enough? We don't know. If the human brain is bound by computability, no.

But the thing on your desktop is not the only type of computer. Are Quantum Computers bound by the limits of Turing Machines? It turns out the answer is yes. But is it possible to build a 'computer' that can do things a Turing Machine can't? We don't know.

All that said, I don't agree with you, I don't think FRACTRAN has any implications about the structure of reality, sorry. It's just a simple set of rules applied to fractional notation. The only thing it demonstrates is the power of a set of rules which we intuitively perceive as weak.

posted by lm: 997 days ago