# 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. – Aryeh Jan 12 '19 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)$. – Andrej Bauer Jan 13 '19 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 – Bananach Jan 13 '19 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. – Andrej Bauer Jan 13 '19 at 18:44
• @AndrejBauer Which close votes? Maybe I can't see them without more reputation? – Bananach Jan 13 '19 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.)