Revolutions in Computer Science
Computer science is, at its core, the study of algorithms. What can we compute, and how fast can we compute it? Its sub-fields, such as image processing, AI, Operating Systems, Programming Languages, numerical computing, etc. can be viewed as answering these questions for specific types of problems.

With that in mind, I think the most major revolution is:

Godel/Turing and Undecidability

The mathematician Hilbert posed a series of problems to the mathematical community. One was to find an algorithm for the Decision problem: that is, to look at any theorem, and state whether it was true or false.

In different ways, Godel and Turing each proved that this was impossible. This revolutionized the way we thought about computation, because for the first time, we had a definitive proof that something could not be computed. No amount of human cleverness could completely solve the problem.

Directly related to this, Turing Machines and the Church-Turing thesis were developed. This formalized what it meant to compute, turned algorithms from things humans talked about into mathematical objects that could be reasoned about, have theorems proved about them. And it established that the two extreme ways of thinking of computation, namely as functions and as transformation of an infinite memory, were equivalent.