"Computer science is no more about computers than astronomy is about telescopes." - Dijkstra
"Computer science is not about machines, in the same way that astronomy is not about telescopes. There is an essential unity of mathematics and computer science." - Fellows
Sure in pure mathematics you can derive solutions using pure logic however if a model looks sound but an example shows up that disagrees with the model then there is obviously a flaw somewhere.
Similarly in physical sciences, experiments are data-points that constrain a model of the system. As physical sciences unfortunately don't have the luxury of using pure logic to derive models, they are stuck with using just these "tests".
As you said computer science is more or less a subset of mathematics. Because of this I would say that they are both true sciences, they just have a few extra tools at their disposal compared to the rest of the sciences.
You could try to say the same thing about psych being implemented by neurons, but it's not directly traceable. You can try building up from neural networks, and backtrack from Freud's drive/defense model, but there is an insurmountable gap in between.