Revolutions in Computer Science TL;DR

What revolutions have there been in computer science, which entirely changed our view about the subject, due to 'one way of thinking' being replaced by 'a new (incompatible) way of thinking' (such as Einsteinian physics replacing Newtonian physics).



To explain a bit further:

I was trying to think about revolutions in computer science, and which one there have been. 
To clarify on what I mean by scientific revolutions: 


  "Those non-cumulative developmental episodes in which an older
  paradigm is replaced on whole or part by an incompatible new one"
  (Kuhn, 1970 p.92)


To give perhaps the most famous example. Einstein's theories of relativity have shown that Newtonian physics is incorrect (it makes metaphysical assumptions, which turned out to be wrong). The paradigm in which General Relativity operates is incompatible with the Newtonian mechanics. Which then led to the reconstruction of science (Vienna circle). 

A friend of mine (I believe correctly) pointed out that Quantum Computing could be one such revolution in computer science. But it has not actually happened yet.

As a software engineer myself, every time I thought of something that I'd consider a revolution, I became unsure if it really was a revolution as the 'paradigms' (methodologies) are not actually replaced and often even compatible with older ways of doing things. And some are pure technological advances (Functional programming after OO, or OO after procedural). Perhaps the application of Lambda Calculus in computer science (programming languages, type theory, ..?)

(Sure VCS was kind of a technological revolution, so if possible, let's keep the answers in computer science theory and not the applications in software engineering)

PS: I could not really find a suitable tag :-(
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.