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.