I wouldn't say that theories we can actually prove are not science. Provable theories become approximations again when you take them out into the field. Also imagine a theory that is at first verified through experimentation, but later proven when found it relies on a mathematical relationship. In general science is not that well-defined. What matters is what knowledge the theories convey.

What most computer scientists don't yet realize is that algorithms are not that important. Their specific solution tailors to a certain context and its testable properties depend on that context. The interesting thing about Dijkstra's shortest path algorithm is not how he actually solved it, but the computational complexity of an optimal solution. If you look at it closely this is not really that interesting either. It does not tell you how to solve your shortest path problems when you're building a large-scale on-line route planner (notice all the context). It's just a little nugget of knowledge that can help you during design.

More powerful examples of computer science are Amdahl's law and the PFTK model for TCP throughput. These give us deeper understanding of the world of computation and networking that can really help engineers, the same way physical laws help engineers.

You can't prove that list.pop in Python is always O(1) (imagine there is a bug in a reference implementation). But you can test that assumption for any given implementation.

Given an implementation of Python, yes, you can prove list.pop will run in some (constant, one would hope) number of clock cycles on an abstract architecture. Building reliable machines to simulate such architectures is part of CS, but not a science.

Science is the construction of abstract models which match observed phenomena.