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 im

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.