Why Turing wasn't wrong?

Question

Computer science is a science and as a science each thesis can be refutable. So, why there is no "major" counter-thesis? After all, Einstein was a well known "genius" and has lived a long life and he has got many opponents. Why isn't it the same case for Turing?

Answer 1

Computer science is a science only by name. In practice, it is a blend of engineering, mathematics, and empirical science.

With that out of the way, here are a few comments about the Church–Turing thesis. First, about the thesis itself. We can think of at least three interpretations of the Church–Turing thesis. Under the first, stronger interpretation, any computation that can be done in the physical world can be modelled by (say) a Turing machine. This is a thesis which indeed can be refuted, and people have tried to refute it, though so far unsuccessfully (Scott Aaronson suggests to regard this as a "law of nature").

The second, weaker interpretation only claims that any computation done in practice (now) can be modelled by a Turing machine. This thesis is essentially correct, though to make it truly correct you need to make it mathematically precise; Nachum Dershowitz and Yuri Gurevich have done just that, though their formulation doesn't necessarily reflect the intuitive content of the thesis.

The third interpretation, very related to the second, is that any pseudocode that we can describe can be implemented on a Turing machine. We use this thesis implicitly whenever we describe and analyze algorithms, both in very theoretical areas (recursion theory, computational complexity, theoretical algorithms and data structures, approximation algorithms) and in more applied areas, in which the pseudocode is often translated to code in practice.

Second, in practice the more interesting thesis is what is sometimes called the Cook–Karp thesis. This thesis states that the class $\mathsf{P}$ embodies all decision problems that can be solved efficiently in practice. In my view, this thesis is dubious. There are three main attacks on this thesis.

The first attack is that the class $\mathsf{P}$ is defined asymptotically, whereas we are interested in problems of finite size. It could be that for practical input size, a problem which is perhaps not in $\mathsf{P}$ can be solved efficiently (for example, small cryptosystems can be broken even if they are secure). Conversely, it could be that a problem is in $\mathsf{P}$ but it cannot be solved efficiently, since the polynomial time "kicks in" only for large problems.

This is very related to the second attack, which is that polynomial time algorithms need not be efficient: they could have a large (big O) constant or a large exponent. A good example for a large constant is fast matrix multiplication algorithms, which are not practical due to the large constant. A good example for a large exponent is deterministic primality testing (the AKS algorithm), which isn't practical due to the large exponent.

A third attack, which is more speculative at this point, is that quantum computers can efficiently solve some problems which we think classical computers cannot. While quantum computers still exist only on paper, unless we believe that there is some fundamental obstacle to constructing them (as some people indeed do, for example Gil Kalai), we have to contend that in the future the class $\mathsf{P}$ would have to be enlarged to the corresponding quantum class $\mathsf{BQP}$.

A related attack states that randomized algorithms can be stronger than deterministic ones: for example randomizes primality testing is practical while the AKS algorithm isn't. However, it is believed that "randomness doesn't help", in the sense that $\mathsf{P}=\mathsf{BPP}$ (which doesn't mean that randomized algorithms can't be faster; it only means that they can only be polynomially faster).