the extended Church-Turing thesis
/ Church -> CHURCH, Turing -> TYOOR-ing /
The ordinary Church-Turing thesis is generous: it cares only about WHETHER something can be computed, not how long it takes. The extended Church-Turing thesis is a far bolder, more demanding cousin. It adds a clause about efficiency: not only can a Turing machine compute anything any reasonable model can, it can do so with at most a polynomial slowdown. In other words, no physically realizable machine can be more than polynomially faster than a standard Turing machine.
Spelled out, the extended thesis claims that any reasonable model of computation can be simulated by a (probabilistic) Turing machine with only polynomial overhead in time. This is exactly what makes the complexity class P (polynomial time) a robust, model-independent notion: if it holds, then 'solvable in polynomial time' means the same thing whether you use a multitape machine, a RAM model, or a real C program. Most everyday models do obey it, the simulations between Turing machines, register machines, and ordinary computers all cost only polynomial factors, which is why theorists freely speak of 'polynomial time' without naming a machine.
But unlike the basic thesis, this stronger version is genuinely under threat. Quantum computing is the prime challenger: Shor's algorithm factors integers in polynomial time on a quantum computer, while no known classical (Turing) algorithm does, and simulating a quantum computer on a classical one seems to require exponential time. If that exponential gap is real, the extended thesis is FALSE for time, which is why many now restate it as 'a quantum Turing machine can simulate any reasonable model with polynomial overhead'. Two honest cautions: first, this remains open, no one has proved classical simulation of quantum computers must be exponential. Second, the extended thesis is about efficiency and is the contested one; the plain Church-Turing thesis, about mere computability, is untouched by any of this, a quantum computer computes exactly the same functions as a Turing machine, just possibly faster on some.
A k-tape Turing machine running in time t can be simulated by a single-tape machine in about t^2 steps, a polynomial blowup, so this respects the extended thesis. But the apparent need for exponential time to simulate a quantum computer factoring a large number is the leading reason to doubt the thesis holds in general.
Polynomial slowdowns (multitape to single-tape) respect the extended thesis; quantum speedups may break it.
Do not confuse this with the basic thesis. The extended thesis is about efficiency and may well be false (quantum computing); the plain Church-Turing thesis, about computability alone, is untouched, quantum computers compute the same functions, not new ones.