recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS (more on background/motivation below) & afaik seems like it could be seen as yet unrecognized but a somewhat related/connected phenomenon, or a flip/mirror side of the CT thesis.have not ever seen this proven as a theorem or a discussion in a paper or book, but think there is some evidence, and may even have a rough (not overly difficult) proof myself. (have some intention to post it depending on the response.) wondered what the experts would think of this.is every nontrivial algorithm Turing-complete?dont see an immediate easy way to disprove this, maybe others have an idea.the CT thesis tells us that computation is very broadly modelled by TMs. if the above was a thm, it would seem to mesh with that broad scope. moreover it would emphasize the importance of complexity theory in discriminating the difference between algorithms, because without the study of complexity of the conversions between them, they are all equivalent in a broad sense.some background: the idea initially occurred to me many yrs ago in studying cellular automata and primitive rules like rule 110.[2] there is a Mathew Cook proof that rule 110 is Turing complete. however, the conversion process for the inputs and outputs is extremely intricate/elaborate. which leads to the conjecture that maybe one can relate all nontrivial algorithms using extremely elaborate conversion processes/subroutines/wrappers. by elaborate, I mean also that the complexity in time/space may be extremely inefficient in some cases. also it would seem that a maybe very primitive computation system like rule 110 along with very timeconsuming conversion on the input and output balances out in some sense. in other words, one can convert primitive languages to complex ones using complex input/output wrappers, and vice versa. also reminiscent of the idea of padding, used in many TCS proofs, which can be a special case of wrapping.by nontrivial, am not sure exactly what is meant right now, but that term is used intentionally to call some analogy with Rices theorem.[3] a proof sketch I have in mind does not use Rices theorem but maybe there is some connection? in any case it means some weak property of algorithms that is somewhat easily fulfilled. its slightly more strict than Recursive, but not much more. and not nec the same defn of trivial in Rices thm but maybe close.in fact if the above theorem could be proven, it might make it easier to prove Turing completeness of many systems eg CAs etcetera, by better understanding this very weak property.to be honest this conjecture is also somewhat influenced/inspired by the Berman-Hartmanis isomorphism conjecture[4] which in its current form is not widely believed but proposes an isomorphism for NP complete problems. the above Turing completeness conjecture seems to suggest maybe some kind of an isomorphism across all algorithms that is based on arbitrary complexity classes (possibly for later study).[1] Applicability of Church-Turing thesis to interactive models of computation [2] Initial conditions for universal Rule 110[3] Rices thm, wikipedia[4] Berman/Hartmanis Isomorphism conjecture slides by Manindra Agrawal
is every nontrivial algorithm Turing-complete?
cc.complexity theory;reference request;computability;turing machines;big picture
Take any non-trivial algorithm with bounded runtime, e.g. AKS primality testing algorithm (I don't think anyone would refer to AKS as trivial). It is not Turing-complete, in fact, no  algorithm with computably bounded runtime can be Turing-complete. (This means that no algorithm which always terminates can be Turing-complete since the run-time of any such algorithm would be computable.)