I have been looking for any reference regarding the term: "Extended Church-Turing Thesis" [some people will call it, Strong Church–Turing Thesis]? Does anyone defined it or it is just people in computer science believed it long years ago.

I read some articles and no one put reference for who defined it. for example:

  • In wikipedia, they write, "The extended Church–Turing thesis, which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory".

  • In book, titled "An introduction to quantum computing" Nothing about reference of this term.

I can go for many pages without explicitly writing the reference of this term.

Thank you.

EDIT: I found this paper which refers to this old paper from 1986: Parallel speedup of sequential machines: a defense of parallel computation thesis by Ian Parberry. In the second page, he wrote, [Similarly, the sequential computation thesis [10] states that time on all "reasonable" sequential machine models is related by a polynomia.]" Sequential computation is the one that can be computed in logical order (from top line to bottom line without doing something else during this computation). So, sequential computation thesis looks like "Extended Church-Turing Thesis", since it says that time on all reasonable "like randomized or any other models" is related by a polynomial. I believe that reference [10] is the one that initiated this term. Reference [10] is: L.M. Goldschlager and A. M. Lister, Computer science: a modern introduction, PrenticeIlall, 1983. So, it is a book. I did not find any copy of this book, so I cannot verify this information. But I think it is clear now. Don't agree!

EDIT2: in Goldreich's textbook "P, NP, and NP-completeness - the basics of computational complexity", Goldreich states the following about The Cobham-Edmonds Thesis,

The Cobham-Edmonds Thesis asserts that the time complexities in any two "reasonable and general" models of computation are polynomially related. That is, a problem has time complexity t in some "reasonable and general" model of computation if and only if it has time complexity poly(t) in the model of single-tape Turing machines.

I don't understand why people did not notice that Cobham-Edmonds Thesis is the same as Extended Church-Turing Thesis?

  • $\begingroup$ Sounds like "was realized gradually in the development of complexity theory" answers your question (if it is accurate). $\endgroup$ – D.W. Nov 5 at 18:07
  • 1
    $\begingroup$ @D.W. Thanks for your comment. I believe it is Not enough, it doesn't answer my question. I want a reference or person who initiated the term. e.g. "Quantum Supremacy" initiated by John Preskill, "efficient algorithm" by Jack Edmonds, etc. So, if there is no reference, then when people realized about this term. It must be a someone who start this, don't agree! $\endgroup$ – user777 Nov 5 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.