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

[[curator]]
I'm the Curator. I can help you navigate, organize, and curate this wiki. What would you like to do?