0
$\begingroup$

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 :-(

$\endgroup$
10
  • 2
    $\begingroup$ "I could not really find a suitable tag" -- that's always a good hint towards a question being offtopic. $\endgroup$
    – Raphael
    Nov 8, 2017 at 21:31
  • 7
    $\begingroup$ This strikes me as a primarily opinion-based question, which would be unsuited. Community votes? $\endgroup$
    – Raphael
    Nov 8, 2017 at 21:31
  • $\begingroup$ @Raphael is it really opinion based though? In the end, two paradigms being incompatible is not really an opinion. Newtonian and Einsteinian physics just are incompatible. I did not consider it opinion based given the description of Kuhn and that example. :) $\endgroup$ Nov 8, 2017 at 22:33
  • 2
    $\begingroup$ What exactly is your question? We need you to articulate a specific, answerable question. I don't see any question in your post, merely a bunch of statements, and we're left to infer what the question is. I encourage you to edit your question to state your question precisely and carefully. Also, do you have a definition of what would qualify for you as a revolution? Everyone might have their own opinion about what constitutes as a revolution, but if you can articulate what criteria you would use to determine what counts as a revolution, that make this more objectively answerable. $\endgroup$
    – D.W.
    Nov 9, 2017 at 2:02
  • 1
    $\begingroup$ Most of CS is not a natural science, but more like mathematics. As in maths, we don't find contradictions since we proved our claims formally, and there's no experiment that can falsify that. Otherwise, we would have proved maths inconsistent. So, there's no possibility of a revolution as in physics which can cause a big shift of mind. At most, we can change our minds on conjectures which are still open problems, if they turn up in a surprising way. E.g. "primes is in P" was quite a surprise. $\endgroup$
    – chi
    Nov 9, 2017 at 9:01

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I'd say this was a revolution in mathematics, giving birth to computer science. $\endgroup$
    – Raphael
    Nov 9, 2017 at 9:52
1
$\begingroup$

I'm very unsure of what are you asking, but here is an answer based on a purely subjective take on your "question":

Here's Moore's law:

The complexity for minimum component costs has increased at a rate of roughly a factor of two per year. Certainly over the short term this rate can be expected to continue, if not to increase. Over the longer term, the rate of increase is a bit more uncertain, although there is no reason to believe it will not remain nearly constant for at least 10 years.

Long story short, it states that the overall processing power of computers doubles every two years.

This has been held true in the past, due to certain hardware advancements such as the silicon chip, but the last 10 - 15 years have started to prove it wrong. Optimizing infrastructure is getting harder and harder. First of all because it has to be quasi - compatible with the old infrastructure. Second, because it has to be better.

Quantum Computing and Engineering is most likely to provide new and better machines in the future. The "revolution" has not yet taken place because constructing compact quantum computers is far from easy. The smallest and fastest quantum computers are currently being produced by D - Wave (coming up second is IBM, I believe). Even though the first quantum computers are not as "fat" as their digital brothers, such as ENIAC, they still occupy to much space to become household items.

Research in quantum computing is still being done. There new quantum algorithms, with much, much better time and space complexity than the classical ones. Here's just a few: Simon's algorithm, Shor's algorithm, Grover's algorithm and the list goes on. When it comes to algorithm optimization, progress is surely being made.

Overall, the only thing speeding down this "quantum computing revolution" (apart from the tendency of most programmers to stick to languages and software that has already been used for a while) is the fact that quantum computers are still to big to fit in a home. And expensive. Laptops and smartphones are, of course, out of the question for the time being.

$\endgroup$
2
  • $\begingroup$ Moore's law being proven wrong does seem like a good one actually! Thanks! $\endgroup$ Nov 8, 2017 at 22:33
  • $\begingroup$ It's a bit misleading to say that the quantum computing revolution is being held back (only) because of size or cost. The main problem seems to be nobody has figured out how to build a quantum computer with more than a few tens of qubits (D-wave doesn't count; it can't run Shor's or Grover's). $\endgroup$ Nov 9, 2017 at 14:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.