Professor Landsman,
I must admit your approach took me back in time to the ancient Greek insight that cosmos/order/certainty came out of or is grounded on chaos/disorder/uncertainty.
If randomness (as apparent lack of patterns and predictability in events ) is a measure of uncertainty, and since outcomes over repeated trials of the same event often follow a probability distribution then the relative frequency over many trials is predictable (so in a way Von Mises was right to derive probability theory from randomness even though he failed in that attempt but helped Kolmogorov succed). In other words randomness could be more fundamental than probability theory that permeates QM and Statistical mechanics since Boltzmann, even though your concept of randomness is in the mathematical sense of Chaitin-Kolmogorov, not Von Mises sense.
Coming back to our theme, if Godel's theorems tells us that the fields of mathematics and physics (according to Hilbert's axiomatic programme) cannot be grounded on logic(in classical and symbolic sense, but who knows maybe one day it could be grounded on a different type of logic, say in Brouwer-Heyting intuitionism or Moisil-Lukasiewicz many valued logic) and Bell's theorem that QM cannot be grounded on classical determinism or any underlying hidden variables theory a la deBroglie-Bohm-Vigier then how do we know that we haven't been using undecidable results to prove our theorems in both mathematics and physics throughout millenia? (like the ones we found in Euclidian geometry so that Hilbert had to re-axiomatize it)
Does this mean that ultimayely, randomness and chaos could be the ground for both mathematics and physics, with their logical necessity and deterministic or indeteministic laws and that ultimately the Greeks were right?...