Formalization and Proof of the "Extended Church-Turing Thesis"

Jenny Falkovich


Abstract:

One of the important parameters in the description of a modern
algorithm is its complexity. This analysis strongly depends on the
underlying computational model and domain representation. But, despite
that, we are used to consider complexity classes like P, NP, or Exp to
be well defined. This invariance relies on the famous "Extended
Church-Turing Thesis", which asserts that every "effective" algorithm
can be simulated by a Turing machine with only a polynomial overhead
in the number of steps. True, this thesis is satisfied by all the
usual "effective" models, and makes one optimistic that the hypothesis
holds generally. Yet, the intriguing possibility of the existence of
more powerful, but still effectively realizable, computational models
than those we have today, remains open.  To prove the thesis from first
principles, one should not rely on any specific computational model,
but rather capture the generic notion of effective algorithm. We
suggest an axiomatic approach, which allows us to investigate the
notion of effective algorithm on the most basic, yet most intuitive,
level.