Houjun Liu

Extended Church-Turing Thesis

A Turing Machine can simulate every “reasonable” model of computation with only Polynomial Time increase in time complexity—possibly the “worse possible”

This is only a thesis! There’s a chance, for instance, randomized quantum algorithms may change this.

see also: Church-Turing thesis as local steps