Recently there was a big response here to a question relating to the Church-Turing (from now on referred to as "CT") thesis . 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.
I 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?
I don't 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.
Here's some background: the idea initially occurred to me many yrs ago in studying cellular automata and primitive rules like rule 110. 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. 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".
In my opinion this conjecture is also somewhat influenced/inspired by the Berman-Hartmanis isomorphism conjecture 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).