Physical reality is a slippery thing. Yes, at the level of our daily life it all seems very solid and obvious, but inspecting that foundation revealed a bewildering world of relativity and uncertainty. And one of the most intriguing ways out of this bewilderment seems to be the "it from bit" trend in physics, which makes information the fundamental reality.
I personally don't feel the need to tie the notion of reality to physical phenomena. I prefer something more along the lines of Philip K. Dick's "reality is that which doesn't go away when you stop believing in it", or, as you put it, "something which exists independently of us". The fact that there are an infinite number of primes, is such a fact. Surely any alien civilization would know this fact. Maths doesn't go away when we look away, and neither does the notion of computation. Sure, Turing machines are a human construct, and there can be others as well. But the Church-Turing thesis speaks about how these constructs all ultimately describe the same underlying reality.