[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/extended_church_turing_thesis.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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 “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