The Church-Turing Thesis or Computability Thesis is an assumption in computer science, developed independently by Alonzo Church and Alan Turing in 1936, which sets a boundary between computable vs. non-computable problems, by relating computable functions to those which can be worked out in finite time by an algorithm, i.e., a set of instructions to be followed by a machine.
Simply stated, it reduced to: everything computable is computable by a Turing machine.
This brings the problem to defining a Turing machine, which can be regarded as a basic, abstract computer. So the thesis becomes: "everything computable is computable by a computer". This then seems to reduce to a tautology. The point is that "computer" or, more precisely, Turing machine, is here to understand as excluding a "magical" or "hyper-computer" that cannot be implemented with transistors, an assembly language, a compiler and a user interface to make a language like C or Julia which could compute the function just the same than the magical computer. If someone can compute it, you can compute it too. This is the Church-Turing machine.
Technically, it establishes an equivalence between the λ calculus of Church and the "logical computing machines" of Turing, which later became known as Turing machines and became central to the thesis (unlike $\lambda$-calculus that was regarded as strong evidence for the same conclusion from an independent approach). Turing showed that a function is λ-computable if and only if it is Turing computable.
In the words of Turing: «a function is effectively calculable if its values can be found by some purely mechanical process».
Importantly, the "thesis" is an assumption. It is not proven. But it is strongly thought to be true.
It is a shaky theoretical construct (whence the name of "thesis" as opposed to "theorem") since it relies on intuitive definition of computationability remains vague.
The Strong Church-Turing Thesis further asserts that any computable function that can be computed efficiently (in polynomial time) in some way, can also be computed efficiently on a probabilistic Turing machine.
According to Yao,[1] (as reported by [1]):
The Extended Church-Turing Thesis (ECT) makes the … assertion that the Turing machine model is also as efficient as any computing device can be. That is, if a function is computable by some hardware device in time T(n) for input of size n, then it is computable by a Turing machine in time $(T(n))^k$ for some fixed k.
Yao points out that ECT has a powerful implication:
at least in principle, to make future computers more efficient, one only needs to focus on improving the implementation technology of present-day computer designs.
A quantum computer would violate this understanding of the Extended Church-Turing thesis.
The Church-Turing thesis, which started as a mathematical/logical problem, acquires a new dimension when bringing physics into the mix and, in particular, the problem of quantum computation. A famous formulation by David Deutsch, now known as the Church-Turing-Deutsch thesis asserts that a universal computing device can simulate every physical process..
Important papers include: