-9

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

user1271772
  • 541
  • 3
  • 16
vzn
  • 11,014
  • 2
  • 31
  • 64
  • 6
    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. – Marzio De Biasi Aug 31 '12 at 16:19
  • 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 Aug 31 '12 at 16:33
  • 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 Aug 31 '12 at 16:43
  • 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 Aug 31 '12 at 16:52
  • 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 Aug 31 '12 at 16:56
  • You seem to be talking about something close to Wolfram's "the Principle of Computational Equivalence" 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 Aug 31 '12 at 17:14
  • 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 Aug 31 '12 at 17:15
  • 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 Aug 31 '12 at 17:20
  • @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 Aug 31 '12 at 17:37
  • and @sasho you didnt prove there is no $w_{out}$ that works for your case true? – vzn Aug 31 '12 at 17:42
  • You can find some related FOM posts Here that discuss the 110 rule. In general I would suggest caution regarding claims made by Wolfram. – Kaveh Aug 31 '12 at 17:48
  • @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 Aug 31 '12 at 17:50
  • For example, things like presetting a nonstandard infinite string in the memory. – Kaveh Aug 31 '12 at 17:52
  • @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 Aug 31 '12 at 18:24
  • @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 Aug 31 '12 at 18:44
  • $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 Aug 31 '12 at 18:47
  • 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 Aug 31 '12 at 18:53
  • 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 Aug 31 '12 at 19:04
  • 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 Aug 31 '12 at 20:31
  • @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 Apr 11 '14 at 17:03

2 Answers2

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.

Jeffε
  • 23,129
  • 10
  • 96
  • 163
9

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183