A Formalization and Proof of the Extended Church-Turing Thesis -Extended   Abstract-
  We prove the Extended Church-Turing Thesis: Every effective algorithm can be efficiently simulated by a Turing machine. This is accomplished by emulating an effective algorithm via an abstract state machine, and simulating such an abstract state machine by a random access machine, representing data as a minimal term graph. 
Nachum Dershowitz (Tel Aviv University), Evgenia Falkovich (Tel Aviv   University)
cs.LO cs.CC