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. 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.We also keep finding ties between computation and mathematics
it suggests that computation is an underlying structure in reality.
To clarify, by 'underlying structure', I don't mean that it is the underlying structure; rather that it appears over and over, similar to fractals or the Fibonnaci sequence. Digital physics is a whole step beyond that that I'm not sure I'm willing to take. Yeah, this one's tricky. If we had a lucky enough human (or magic coin), we could probably show P=NP, which is probably why P?=NP is so difficult to decide. I reckon probably even humans can't always decide the halting problem (and even if they could, augmenting a Turing machine with a human smart enough to decide if a TM halts introduces an entirely different and more difficult halting problem). Even so, we don't really understand what 'intuition' is, so it may very well be true that there are uncomputable functions that humans can define. You might find this article on Bongard problems, among other things interesting.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.
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.
Is "the theory of everything'' merely the ultimate ensemble theory? is also a rather interesting article to read, although it tackles the problem from a different angle.