<p><strong>Not even no.</strong></p>

<p>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 <em>can</em> be Turing-complete are usually called <em>models of computation</em>.</p>

CC BY-SA 3.0
2012-08-31T20:03:56.760Z
2012-08-31T20:03:56.760Z
Jeffε
<p>Take any non-trivial algorithm with bounded runtime, e.g. <a href="http://en.wikipedia.org/wiki/AKS_primality_test">AKS primality testing algorithm</a> (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.)</p>

CC BY-SA 3.0
2012-08-31T16:54:43.770Z
2012-08-31T18:02:07.790Z
2012-08-31T18:02:07.790Z
Kaveh
<p>Recently there was a big response here to a question relating to the Church-Turing (from now on referred to as &quot;CT&quot;) 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) &amp; 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.</p>
<p>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.</p>
<blockquote>
<p>is every &quot;nontrivial&quot; algorithm Turing-complete?</p>
</blockquote>
<p>I don't see an immediate easy way to disprove this, maybe others have an idea.</p>
<p>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 &quot;equivalent&quot; in a broad sense.</p>
<p>Here's 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/&quot;wrappers&quot;. by elaborate, I mean also that the complexity in time/space may be extremely inefficient in some cases.</p>
<p>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 &quot;wrappers&quot;, and vice versa. also reminiscent of the idea of &quot;padding&quot;, used in many TCS proofs, which can be a special case of wrapping.</p>
<p>By &quot;nontrivial&quot;, 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 &quot;weak&quot; 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 &quot;trivial&quot; in Rices thm but maybe close.</p>
<p>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 &quot;weak property&quot;.</p>
<p>In my opinion 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).</p>
<ul>
<li>[1] <a href="https://cstheory.stackexchange.com/questions/12377/applicability-of-church-turing-thesis-to-interactive-models-of-computation">Applicability of Church-Turing thesis to interactive models of computation </a></li>
<li>[2] <a href="https://cstheory.stackexchange.com/questions/11002/initial-conditions-for-universal-rule-110">Initial conditions for universal Rule 110</a></li>
<li>[3] <a href="http://en.wikipedia.org/wiki/Rices_theorem" rel="nofollow noreferrer">Rices thm, wikipedia</a></li>
<li>[4] <a href="http://www.cse.iitk.ac.in/users/manindra/presentations/CiE%20Talk.pdf" rel="nofollow noreferrer">Berman/Hartmanis Isomorphism conjecture slides by Manindra Agrawal</a></li>
</ul>

CC BY-SA 3.0
2012-08-31T16:19:33.453Z
Usually "[turing completeness](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Algorithm)" otherwise (IMO) the question is senseless.
Marzio De Biasi
CC BY-SA 3.0
2012-08-31T16:33:16.173Z
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.
vzn
CC BY-SA 3.0
2012-08-31T16:43:07.767Z
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)))$
vzn
CC BY-SA 3.0
2012-08-31T16:52:06.253Z
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)?!?)
Marzio De Biasi
CC BY-SA 3.0
2012-08-31T16:56:57.713Z
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.
vzn
CC BY-SA 3.0
2012-08-31T17:14:01.693Z
You seem to be talking about something close to Wolfram's "[the Principle of Computational Equivalence](http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html)" claim which is not widely accepted by experts (in fact, I don't know any expert on the topic who has accepted his claim).
Kaveh
CC BY-SA 3.0
2012-08-31T17:15:06.230Z
yeah, admit this is similar to some of wolframs ideas, avoided citing him on purpose because he's persona non grata among many. was not aware there was still controversy over whether rule 110 is Turing complete, thought it was settled years ago. to me this formulation of some of the issues captures some of the difficulty formally. but may have botched it somewhat. anyway you refer to std defn of Turing completeness, but Im trying to capture that here somewhat formally. what std defn are you referring to?
vzn
CC BY-SA 3.0
2012-08-31T17:20:04.263Z
say $f$ and $g$ output 0 or 1 and $g$ outputs 0 at least for one input (call it $x_0$), and outputs 1 for at least 1 input (call it $x_1$). $w_{in}(x)$ computes $f(x)$ and if $f(x) = 0$ outputs $x_0$, o/w outputs $x_1$. decidability of equivalence has no bearing because we design the wrappers to be equivalent  to $g$ or not. do you have something in mind which is different/excludes this trivial construction?
Sasho Nikolov
CC BY-SA 3.0
2012-08-31T17:37:19.060Z
@sasho good pt. I think it works for functions that have "increasing" inputs and outputs. they dont have to be monotonically increasing (in size), but "increasing". Im looking for the correct precise definition of "increasing". it might even just be "infinite" for the outputs. ie not a finite number of outputs. (then maybe there might be a way to generalize to fns that have finite outputs as in your case, by creating a related function with infinite outputs out of one that has only finite outputs)
vzn
CC BY-SA 3.0
2012-08-31T17:42:00.893Z
and @sasho you didnt prove there is no $w_{out}$ that works for your case true?
vzn
CC BY-SA 3.0
2012-08-31T17:48:40.093Z
You can find some related FOM posts [Here](http://www.google.com/search?q=site:cs.nyu.edu%20fom%20Turing%20complete%20wolfram) that discuss the 110 rule. In general I would suggest caution regarding claims made by Wolfram.
Kaveh
CC BY-SA 3.0
2012-08-31T17:50:06.123Z
@kaveh.. define "cheating"... no $w_{out}$? yes I have seen some old FOM debate on the subj. the problem is that Turing equivalence actually seems not to have a strict formal definition anywhere.... hence an attempt to sketch it out here and add an implication....
vzn
CC BY-SA 3.0
2012-08-31T17:52:21.237Z
For example, things like presetting a nonstandard infinite string in the memory.
Kaveh
CC BY-SA 3.0
2012-08-31T18:24:02.510Z
@kaveh as I understand it cook did indeed use infinite repeating periodic patterns for encode/decode into his machine (CA110). hence my defining $w_{in}$ and $w_{out}$ respectively. that seems to capture some of the issue. anyway I definitely botched this by talking about "algorithms" instead of "semialgorithms" in the above post, but will try to work it out some more
vzn
CC BY-SA 3.0
2012-08-31T18:44:55.507Z
@sasho sorry skimmed your example & see you are basically defining $w_{in}(x)=f(x)$? and $w_{out}(x)=x$? anyway the point of all this is that the above construction (defining encoders/decoders) is what goes on in Turing completeness/equivalence proofs even including Turings original proof, to some degree. yes I do have an example that is not quite as trivial.... but to evaluate Turing equivalence proofs, one must define and consider $w_{in}$ and $w_{out}$, which become quite complex in the CA proofs, and exactly the issue of whether "cheating" is going on is raised...!
vzn
CC BY-SA 3.0
2012-08-31T18:47:31.940Z
$w_{out}$ is identity in my case. if you don't like that you can flip bits. generalizing to larger domains is easy; all you need is that the range of $g$ to be at least as large as the range of $f$.
Sasho Nikolov
CC BY-SA 3.0
2012-08-31T18:53:57.780Z
ok. please pick some restriction on the wrappers that rules out cheating, update the question and then it becomes possible to think about this. if you do not know how to restrict the wrappers, then maybe that should be your question.
Sasho Nikolov
CC BY-SA 3.0
2012-08-31T19:04:37.720Z
the point is that wrt the CA110 controversy apparently _even the mainstream TCS community_ does not have a std definition about "avoiding cheating" in Turing equivalence proofs! and perhaps maybe _one does not exist_ due to this phenomenon. even excluding the obvious $w_{in}(x), w_{out}(x) \neq g(x), f(x)$ does not seem to fix the problem because there are still very similar functions to $g(x)$ and $f(x)$ that satisfy it. therefore the only sensible definition of Turing completeness seems to inherently consider the _complexity_ of $w_{in}, w_{out}$... right?
vzn
CC BY-SA 3.0
2012-08-31T20:31:47.093Z
hint: this probably has to do with the guaranteed existing canonical ordering of words in recursive languages & I think it can be extended to recursively enumerable...
vzn
CC BY-SA 3.0
2014-04-11T17:03:10.490Z
@vzn: two weeks ago I ordered ANKS (I included it in the order out of curiosity)  ... after (partially) reading it I now understand what you probably meant with "nontrivial" ... "nontrivial as interpreted by Stephan Wolfram" ... it turns out that a question similar to yours is one of the central questions (or better assertions) of ANKS. Did you read it? (I think that there is also an online version)
Marzio De Biasi
<cc.complexity-theory><reference-request><computability><turing-machines><big-picture>
Is every "nontrivial" algorithm Turing-complete?
vzn
# Is every "nontrivial" algorithm Turing-complete?

(Asked by: username_0 on 2012-08-31)

Recently there was a big response here to a question relating to the Church-Turing (from now on referred to as "CT") 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.

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.[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".

In my opinion 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](https://cstheory.stackexchange.com/questions/12377/applicability-of-church-turing-thesis-to-interactive-models-of-computation)
* [2] [Initial conditions for universal Rule 110](https://cstheory.stackexchange.com/questions/11002/initial-conditions-for-universal-rule-110)
* [3] [Rices thm, wikipedia](http://en.wikipedia.org/wiki/Rices_theorem)
* [4] [Berman/Hartmanis Isomorphism conjecture slides by Manindra Agrawal](http://www.cse.iitk.ac.in/users/manindra/presentations/CiE%20Talk.pdf)

**Tags:** cc.complexity-theory, reference-request, computability, turing-machines, big-picture
> **Comments:**
> **username_1**: Usually "[turing completeness](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Algorithm)" otherwise (IMO) the question is senseless.  
> **username_0**: 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.  
> **username_0**: 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)))$  
> **username_1**: 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)?!?)  
> **username_0**: 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.  
> **username_2**: You seem to be talking about something close to Wolfram's "[the Principle of Computational Equivalence](http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html)" claim which is not widely accepted by experts (in fact, I don't know any expert on the topic who has accepted his claim).  
> **username_0**: yeah, admit this is similar to some of wolframs ideas, avoided citing him on purpose because he's persona non grata among many. was not aware there was still controversy over whether rule 110 is Turing complete, thought it was settled years ago. to me this formulation of some of the issues captures some of the difficulty formally. but may have botched it somewhat. anyway you refer to std defn of Turing completeness, but Im trying to capture that here somewhat formally. what std defn are you referring to?  
> **username_3**: say $f$ and $g$ output 0 or 1 and $g$ outputs 0 at least for one input (call it $x_0$), and outputs 1 for at least 1 input (call it $x_1$). $w_{in}(x)$ computes $f(x)$ and if $f(x) = 0$ outputs $x_0$, o/w outputs $x_1$. decidability of equivalence has no bearing because we design the wrappers to be equivalent  to $g$ or not. do you have something in mind which is different/excludes this trivial construction?  
> **username_0**: @sasho good pt. I think it works for functions that have "increasing" inputs and outputs. they dont have to be monotonically increasing (in size), but "increasing". Im looking for the correct precise definition of "increasing". it might even just be "infinite" for the outputs. ie not a finite number of outputs. (then maybe there might be a way to generalize to fns that have finite outputs as in your case, by creating a related function with infinite outputs out of one that has only finite outputs)  
> **username_0**: and @sasho you didnt prove there is no $w_{out}$ that works for your case true?  
> **username_2**: You can find some related FOM posts [Here](http://www.google.com/search?q=site:cs.nyu.edu%20fom%20Turing%20complete%20wolfram) that discuss the 110 rule. In general I would suggest caution regarding claims made by Wolfram.  
> **username_0**: @kaveh.. define "cheating"... no $w_{out}$? yes I have seen some old FOM debate on the subj. the problem is that Turing equivalence actually seems not to have a strict formal definition anywhere.... hence an attempt to sketch it out here and add an implication....  
> **username_2**: For example, things like presetting a nonstandard infinite string in the memory.  
> **username_0**: @kaveh as I understand it cook did indeed use infinite repeating periodic patterns for encode/decode into his machine (CA110). hence my defining $w_{in}$ and $w_{out}$ respectively. that seems to capture some of the issue. anyway I definitely botched this by talking about "algorithms" instead of "semialgorithms" in the above post, but will try to work it out some more  
> **username_0**: @sasho sorry skimmed your example & see you are basically defining $w_{in}(x)=f(x)$? and $w_{out}(x)=x$? anyway the point of all this is that the above construction (defining encoders/decoders) is what goes on in Turing completeness/equivalence proofs even including Turings original proof, to some degree. yes I do have an example that is not quite as trivial.... but to evaluate Turing equivalence proofs, one must define and consider $w_{in}$ and $w_{out}$, which become quite complex in the CA proofs, and exactly the issue of whether "cheating" is going on is raised...!  
> **username_3**: $w_{out}$ is identity in my case. if you don't like that you can flip bits. generalizing to larger domains is easy; all you need is that the range of $g$ to be at least as large as the range of $f$.  
> **username_3**: ok. please pick some restriction on the wrappers that rules out cheating, update the question and then it becomes possible to think about this. if you do not know how to restrict the wrappers, then maybe that should be your question.  
> **username_0**: the point is that wrt the CA110 controversy apparently _even the mainstream TCS community_ does not have a std definition about "avoiding cheating" in Turing equivalence proofs! and perhaps maybe _one does not exist_ due to this phenomenon. even excluding the obvious $w_{in}(x), w_{out}(x) \neq g(x), f(x)$ does not seem to fix the problem because there are still very similar functions to $g(x)$ and $f(x)$ that satisfy it. therefore the only sensible definition of Turing completeness seems to inherently consider the _complexity_ of $w_{in}, w_{out}$... right?  
> **username_0**: hint: this probably has to do with the guaranteed existing canonical ordering of words in recursive languages & I think it can be extended to recursively enumerable...  
> **username_1**: @vzn: two weeks ago I ordered ANKS (I included it in the order out of curiosity)  ... after (partially) reading it I now understand what you probably meant with "nontrivial" ... "nontrivial as interpreted by Stephan Wolfram" ... it turns out that a question similar to yours is one of the central questions (or better assertions) of ANKS. Did you read it? (I think that there is also an online version)  

---

## 2 answers

### Answer by username_2 on 2012-08-31. Score: 9 | Accepted answer

Take any non-trivial algorithm with bounded runtime, e.g. [AKS primality testing algorithm](http://en.wikipedia.org/wiki/AKS_primality_test) (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.)


---

### Answer by username_4 on 2012-08-31. Score: 17

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


---

