Editing Church–Turing thesis (section)

== Variations ==
The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the '''physical Church–Turing thesis''' states: "All physically computable functions are Turing-computable."<ref>{{cite journal |author-link=Gualtiero Piccinini |author-last=Piccinini |author-first=Gualtiero |date=January 2007 |url=http://www.umsl.edu/~piccininig/Computationalism_Church-Turing_Thesis_Church-Turing_Fallacy.pdf |archive-url=https://web.archive.org/web/20080424151259/http://www.umsl.edu/~piccininig/Computationalism_Church-Turing_Thesis_Church-Turing_Fallacy.pdf |archive-date=2008-04-24 |url-status=live |title=Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy |doi=10.1007/s11229-005-0194-z |journal=Synthese |volume=154 |issue=1 |pages=97–120 |citeseerx=10.1.1.360.9796 |s2cid=494161}}</ref>{{rp|page=101}}

{{anchor|complexity-theoretic Church–Turing thesis}}The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate another. It has been proved for instance that a (multi-tape) [[universal Turing machine]] only suffers a logarithmic slowdown factor in simulating any Turing machine.<ref>{{cite book |author-last1=Arora |author-first1=Sanjeev |author-last2=Barak |author-first2=Boaz |url=http://www.cs.princeton.edu/theory/complexity/ |title=Complexity Theory: A Modern Approach |publisher=[[Cambridge University Press]] |date=2009 |isbn=978-0-521-42426-4}} Sections 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9".</ref>

A variation of the Church–Turing thesis addresses whether an arbitrary but "reasonable" model of computation can be efficiently simulated. This is called the '''feasibility thesis''',<ref>{{cite web |title=Official Problem Description |url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf |archive-date=2005-11-24 |archive-url=https://web.archive.org/web/20051124084833/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf}}</ref> also known as the ('''classical''') '''complexity-theoretic Church–Turing thesis''' or the '''extended Church–Turing thesis''', which is not due to Church or Turing, but rather was realized gradually in the development of [[Computational complexity theory|complexity theory]]. It states:<ref name="kaye">{{cite book |author-first1=Phillip |author-last1=Kaye |author-first2=Raymond |author-last2=Laflamme |author-first3=Michele |author-last3=Mosca |title=An introduction to quantum computing |publisher=Oxford University Press |date=2007 |isbn=978-0-19-857049-3 |pages=5–6}}</ref> "A [[probabilistic Turing machine]] can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to [[polynomial-time reduction]]s. This thesis was originally called '''computational complexity-theoretic Church–Turing thesis''' by Ethan Bernstein and [[Umesh Vazirani]] (1997). The complexity-theoretic Church–Turing thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial time ([[Bounded-error probabilistic polynomial|BPP]]) equals deterministic polynomial time ([[P (complexity)|P]]), the word 'probabilistic' is optional in the complexity-theoretic Church–Turing thesis. A similar thesis, called the '''invariance thesis''', was introduced by Cees F. Slot and Peter van Emde Boas. It states: {{"'}}Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space."<ref>{{cite book |author-first=Peter |author-last=van Emde Boas |chapter=Machine Models and Simulations |title=Handbook of Theoretical Computer Science A |publisher=[[Elsevier]] |date=1990 |page=5}}</ref> The thesis originally appeared in a paper at [[Symposium on Theory of Computing|STOC]]'84, which was the first paper to show that polynomial-time overhead and constant-space overhead could be ''simultaneously'' achieved for a simulation of a [[Random Access Machine]] on a Turing machine.<ref>{{cite conference |author-first1=C. |author-last1=Slot |author-first2=P. |author-last2=van Emde Boas |title=On tape versus core: an application of space efficient perfect hash functions to the invariance of space |conference=[[Symposium on Theory of Computing|STOC]] |date=December 1984}}</ref>

If [[BQP]] is shown to be a strict superset of [[Bounded-error probabilistic polynomial|BPP]], it would invalidate the complexity-theoretic Church–Turing thesis. In other words, there would be efficient [[quantum algorithms]] that perform tasks that do not have efficient [[probabilistic algorithms]]. This would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but it would invalidate the classical complexity-theoretic Church–Turing thesis for efficiency reasons. Consequently, the '''quantum complexity-theoretic Church–Turing thesis''' states:<ref name="kaye"/> "A [[quantum Turing machine]] can efficiently simulate any realistic model of computation."

Eugene Eberbach and Peter Wegner claim that the Church–Turing thesis is sometimes interpreted too broadly,
stating "Though [...] Turing machines express the behavior of algorithms, the broader assertion that algorithms precisely capture what can be computed is invalid".<ref>{{harvnb|Eberbach|Wegner|2003|page=287}}.</ref> They claim that forms of computation not captured by the thesis are relevant today,
terms which they call [[hypercomputation|super-Turing computation]].