---
title: "Extended Church-Turing Thesis"
type: concept
source: https://www.jemoka.com/posts/kbhextended_church_turing_thesis/
confidence: high
status: active
---

A Turing Machine can simulate every &ldquo;reasonable&rdquo; model of computation with only Polynomial Time increase in time complexity&mdash;possibly the &ldquo;worse possible&rdquo;
This is only a thesis! There&rsquo;s a chance, for instance, randomized quantum algorithms may change this.
see also: Church-Turing thesis as local steps
