# Do Turing complete languages automatically have efficient algorithms [closed]

Every Turing complete programming language can describe an algorithm that sorts sequences. Is it also true that every Turing complete language can describe an algorithm that sorts sequences in $$\mathcal{O}(n \log n)$$ steps?

I don't have a good understanding of theoretical computer science. If the question is dumb, please consider writing a dumbed down answer too.

• I don't think this is true for THE original Turing-complete language: i.e., that of Turing machines! At least not for the deterministic, single-tape case. Jan 12, 2019 at 23:25
• This is not a research-level question, and the answer is "obviously not". Consider a variation of Turing machines, let's call them Bananach machines, where every machine is defined to first write out $2^n$ symbols on an auxiliary "waste" tape, where $n$ is the length of the input. After that, the machine behaves like a Turing machine. Every algorithm we run on a Bananach machine has time complexity at least $\mathcal{O}(2^n)$. Jan 13, 2019 at 10:51
• @AndrejBauer I suspected this. Do you know where I could have asked this instead? Also, to make this more challenging for you, is there a property that we can add to our set of machines that makes the answer "yes"? Or is there any way to make a meaningful statement about this topic at all? I'm just a regular programmer and I wondered why Turing completeness is brought up in programming language wars when it really still leaves a lot of room for one language to be "better" than another. I felt common programming languages are more similar to another besides just all being Turing complete Jan 13, 2019 at 14:28
• The right forum is cs.stackexchange.com and I think some of the close votes suggest that explicitly. I understand it's difficult to find the right forum. You are perfectly correct that there is much more to programming languages than "they're all equivalent to Turing machines". Bringing up Turing machines in a random argument about programming languages is usually just a display of insufficient expertise. At PL conferences nobody mentions Turing machines, unless they're actually relevant. Jan 13, 2019 at 18:44
• @AndrejBauer Which close votes? Maybe I can't see them without more reputation? Jan 13, 2019 at 19:18

I don't have reputation enough to comment, but I don't think it's a stupid question at all (though it may not be appropriate for cstheory). The answer is no, it is not at all guaranteed; in fact, there are proofs to the contrary. For single-tape Turing machines, there apparently is a result on the complexity of optimal sorting routines by Juraj Wiedermann (1992): Optimal Algorithms for Sorting on Single-tape Turing machines. Unfortunately, I'm not able to access a copy. (Note that there's an answer on StackOverflow, asserting that the lower bound on big-O complexity for a single-tape machine has been proved to be $$O(n^2 log(n))$$, but I haven't been able to verify that.)

More recent work is available which discusses off-line Turing machines -- these are Turing machines which, besides the usual working tape, have access to an "input tape" which contains the input to the problem. The input tape is read-only, and the head cannot be moved beyond the bounds of the input. For these machines, complexity of an optimal sorting routine is given by Petersen (2008): Element Distinctness and Sorting on One-Tape Off-Line Turing Machines.

• Very interesting! Is there a reason then that it seems all commonly used programming languages seem to behave equal in terms of complexity? Jan 13, 2019 at 6:32
• The reason must be that when people design a programming language they try to make sure it can efficiently simulate a standard model, like multi-tape Turing machines or word RAM. (What I am saying is a little ill defined because a programming language doesn't automatically come with sensible complexity measure, I think.) Jan 13, 2019 at 16:15

No such a statement is not guaranteed, however, there is an extended Church-Turing thesis which states very similar statement.