Note that the formulation of these are counter-examples and thus assert a fundamental limit of computation, but it says nothing that there might be many other things that are non-computable that do not fit the form of these counter-examples.
I've heard it referred to as the Church–Turing–Deutsch principle [1], since Deutsch talked about the physical version of it.
I think it's interesting that the assumption that nature is computable comes so naturally, even though as far as I can tell it's entirely unclear whether it is or not. In particular, Deutsch points out that if the universe needs reals that includes a whole bunch of noncomputable numbers, and in fact our favorite model of physics for a significant chunk of history ('classical physics') did require reals and so was noncomputable.
I also tend to assume that nature is computable, but I don't think these assertions have really "held up for a damn long time".
As well as the fact that we managed with not much of a model followed by a noncomputable one for most of history, it seems to me that there might be a bias towards finding computable models over noncomputable models, which makes any reasoning based on observing that we've found a bunch of computable models suspect.
[1] https://en.wikipedia.org/wiki/Church-Turing-Deutsch_principl...
"When you get deep enough, mathematics is in fact reducible to computation (paging Robert Harper)."
Could you elaborate on that, as it seems to be a big jump? I'm not familiar with Harper's work (I'm assuming you mean this [1] Robert Harper). I'm also not a mathematician...
[1] http://en.wikipedia.org/wiki/Robert_Harper_(computer_scienti...
[2] Or, presumably, Lambda calculus or Godelian recursion.
http://existentialtype.wordpress.com/2011/03/27/the-holy-tri...
http://www.doc.ic.ac.uk/~gds/PLMW/harper-plmw13-talk.pdf
Types are propositions! Programs are mappings! Computation is proof!
These are the truths of this world! Submit to those truths, you webdevs in human clothing ;-)!
(I'm always hoping someone will catch the obscure references I throw into my comments, but alas.)
So far, everything in reality seems to be "made of" either determinism or randomness. There might be a third option (and options beyond that), but we haven't seen one or thought of one yet.
So far, computation can model determinism perfectly well (after all, computation is just very orderly, bottled-up determinism harnessed to a predictable human purpose!), and model randomness as well by drawing random bits from an entropy source. When you get deep enough, mathematics is in fact reducible to computation (paging Robert Harper). Given this, the Church-Turing Thesis says that our mechanical computers ought to be able to model anything reality is made of: either reality is theoretically Turing-recognizable given enough compute-power, or reality contains super-Turing phenomena that we could exploit to build super-Turing computers.
Thus, if we accept a couple of assertions that have held up decently so far, it looks as if all parts of our prosaic, everyday reality ought to be amenable to computational modeling, provided we find the right model and throw enough flops at it.
They are assertions, but they've also held up for a damn long time, and we would need some extraordinary evidence to accept the extraordinary claim that those assertions don't hold.