Theoretical computer science would exist even if there were no computers. Computer science is not bound by the laws of physics; it is inspired by them but, like mathematics, it is something that is completely invented by man.
Not true! Long before Australopithecus or even Dilpodous walked the earth, ages before the primoridal slime dreamed of phtosynthesis, eons before the sun coalesced from the scattered ashes of its garishly suicidal parents, 2+2 was 4, π was transcendental, any formal system powerful enough to include arithmetic admitted true but unprovable statements, and comparison-based sorting algorithms required Ω(n log n) time. These are not mere human inventions, Bernard, but deeply humbling discoveries. These are necessary truths, in a far more fundamental sense than the so-called laws of physics.
Scott gets a little closer:
The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They're a great way to illustrate the point, they were probably essential for discovering the point, but they're not the point. The best definition of complexity theory I can think of is that it's quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods.
Update (Feb 19): Bernard graciously points me to his longer essay, in which he not only hits the target smack in the center, but fires several arrows directly into their predecessors' feathery back ends. Load up your iPod with verlan-laced rap, or perhaps some vintage Wesley Willis, and read the whole thing.