Public View
Suggest
Download this page (.md) Download entire wiki (.zip)
Clone entire wiki

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

Page updated