In the twentieth century we learned that math is bigger than we can possibly handle with anything like traditional mathematical rigor. There is no contradiction in saying one is running an experiment on math when it is not possible even in theory to obtain the result of the experiment through any means more efficient than simply running the experiment. And given Computer Science's focus on things that are, generally, Turing Complete, proving that that is frequently the case is a sophomore-level homework problem in any decent curriculum. (See "Rice's Theorem".)

The idea of "math" you get in school is not wrong, but very incomplete. "Experimental math" is a perfectly valid field of study; mathematics itself proved it, about a hundred years ago. Theories are made, predictions are given, and there's no way to prove or disprove them until the experiment is run, at which point you still only have evidence, not proof (in general); sounds pretty scientific to me.

Some aspects of programming languages are very math heavy - things like type theory and lambda calculus. It's accurate to say some of the field of programming language design and implementation depends on math. Hence, I'm willing to say the field aggregate has that dependence, even if some other parts of the field do not have an explicit dependence.