It is not clear that our universe has infinite computing power. If it is finite, then there is a finite complete description of it. Maybe that finite description even fits in the universe. But we can't, in the universe, compute all the consequences of the description. If the universe is infinite and able to simulate infinite Turing machines, such as Conway's game of Life, then Gödel's theorem applies, as others explain. There are also intermediate possibilities, such as the universe is infinite, but we are not able to exploit it for computation, but a positivist might classify that as finite. I think that the state of the art is that this is the case, due to the cosmological constant.