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

  • 6
    $\begingroup$ Usually "turing completeness" refers to a system of data-manipulation rules (e.g. a 2-tag system); so you should clarify what do you mean with "nontrivial algorithm" otherwise (IMO) the question is senseless. $\endgroup$ – Marzio De Biasi Aug 31 '12 at 16:19
  • $\begingroup$ hmm. how about this. let $f(x)$ and $g(x)$ be any two nontrivial algorithms. then $f(x)$ can be used to compute $g(x)$ and vice versa, using suitably complex "input & output conversion wrappers". since $TM(x)$, the universal Turing machine is Turing complete, is also nontrivial, then it can be substituted for either $f(x)$ or $g(x)$, proving that all algorithms are Turing complete. $\endgroup$ – vzn Aug 31 '12 at 16:33
  • $\begingroup$ or more specifically let $w_{in}(x)$ and $w_{out}(x)$ be the "input and output conversion wrappers." such wrappers (albeit some complex) always exist such that $f(x)$=$w_{out}(g(w_{in}(x)))$ $\endgroup$ – vzn Aug 31 '12 at 16:43
  • $\begingroup$ still not clear what is a "nontrivial algorithm"; "nontrivial" in the context of Rice's theorem is a proper non empty subset of the class of unary partial computable functions. Furthermore it is not clear what is a "suitably complex I/O wrapper" (you can use g(x) itself as a wrapper for computing g(x)?!?) $\endgroup$ – Marzio De Biasi Aug 31 '12 at 16:52
  • $\begingroup$ but, @Marzio, isnt that kind of a problem because the question of whether two algorithms are equivalent is undecidable. ie its not decidable if a given wrapper $w_{in}$ or $w_{out}$ is actually "equivalent" to $g(x)$.. true? however I do have some "wrappers" in mind that are provably not equivalent. $\endgroup$ – vzn Aug 31 '12 at 16:56

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.)

| cite | improve this answer | |

Not even no.

Algorithms are not the right class of objects to be Turing-complete; asking whether an algorithm is Turing-complete is like asking whether a cat is prime. Objects that can be Turing-complete are usually called models of computation.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.