<p>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): <a href="https://dl.acm.org/citation.cfm?id=660033" rel="nofollow noreferrer">Optimal Algorithms for Sorting on Single-tape Turing machines</a>. Unfortunately, I'm not able to access a copy. (Note that there's <a href="https://stackoverflow.com/questions/29566714/can-a-turing-machine-perform-quicksort">an answer on StackOverflow</a>, asserting that the lower bound on big-O complexity for a single-tape machine has been proved to be <span class="math-container">$O(n^2 log(n))$</span>, but I haven't been able to verify that.)</p>

<p>More recent work is available which discusses <em>off-line Turing machines</em> -- 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): <a href="https://link.springer.com/chapter/10.1007/978-3-540-77566-9_35" rel="nofollow noreferrer">Element Distinctness and Sorting on One-Tape Off-Line Turing Machines</a>.</p>

CC BY-SA 4.0
2019-01-13T06:32:09.800Z
Very interesting! Is there a reason then that it seems all commonly used programming languages seem to behave equal in terms of complexity?
Bananach
CC BY-SA 4.0
2019-01-13T16:15:39.183Z
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.)
Sasho Nikolov
CC BY-SA 4.0
2019-01-13T04:34:42.593Z
2019-01-13T06:42:21.527Z
2019-01-13T06:42:21.527Z
phlummox
<p>No such a statement is not guaranteed, however, there is an extended <a href="https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis" rel="nofollow noreferrer">Church-Turing thesis</a> which states very similar statement.</p>

CC BY-SA 4.0
2019-01-13T06:31:56.017Z
Could you extend your answer to include that very similar statement? I cannot find it following the link in your answer
Bananach
CC BY-SA 4.0
2019-01-14T23:54:25.597Z
I was talking about the extended Church-Turing thesis (note that it is not a theorem), which states that a probabilistic Turing machine can efficiently simulate any realistic model of computation. This thesis partially answers your question about the programming languages since almost all of them are "realistic".
knop
CC BY-SA 4.0
2019-01-12T22:42:01.257Z
2019-01-12T22:42:01.257Z
knop
<p>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 <span class="math-container">$\mathcal{O}(n \log n)$</span> steps?</p>

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

CC BY-SA 4.0
2019-01-12T23:25:47.983Z
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
CC BY-SA 4.0
2019-01-13T10:51:54.767Z
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
CC BY-SA 4.0
2019-01-13T14:28:15.667Z
@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
CC BY-SA 4.0
2019-01-13T18:44:35.350Z
The right forum is https://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
CC BY-SA 4.0
2019-01-13T19:18:55.347Z
@AndrejBauer Which close votes? Maybe I can't see them without more reputation?
Bananach
CC BY-SA 4.0
2019-01-13T19:27:32.770Z
Ah, you'll see them once there are sufficiently many to close down the question :-)
Andrej Bauer
<cc.complexity-theory><turing-machines>
Do Turing complete languages automatically have efficient algorithms
Bananach
# Do Turing complete languages automatically have efficient algorithms

(Asked by: username_0 on 2019-01-12)

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.

**Tags:** cc.complexity-theory, turing-machines

> **Comments:**
> **username_1**: 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.  
> **username_2**: This is not a research-level question, and the answer is "obviously not". Consider a variation of Turing machines, let's call them *username_0 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 username_0 machine has time complexity at least $\mathcal{O}(2^n)$.  
> **username_0**: @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  
> **username_2**: The right forum is https://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.  
> **username_0**: @AndrejBauer Which close votes? Maybe I can't see them without more reputation?  
> **username_2**: Ah, you'll see them once there are sufficiently many to close down the question :-)  

---

## 2 answers

### Answer by username_3 on 2019-01-13. Score: 3 | Accepted answer

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](https://dl.acm.org/citation.cfm?id=660033). Unfortunately, I'm not able to access a copy. (Note that there's [an answer on StackOverflow](https://stackoverflow.com/questions/29566714/can-a-turing-machine-perform-quicksort), 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](https://link.springer.com/chapter/10.1007/978-3-540-77566-9_35).

> **Comments:**
> **username_0**: Very interesting! Is there a reason then that it seems all commonly used programming languages seem to behave equal in terms of complexity?  
> **username_4**: 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.)  

---

### Answer by username_5 on 2019-01-12. Score: 0

No such a statement is not guaranteed, however, there is an extended [Church-Turing thesis](https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis) which states very similar statement.

> **Comments:**
> **username_0**: Could you extend your answer to include that very similar statement? I cannot find it following the link in your answer  
> **username_5**: I was talking about the extended Church-Turing thesis (note that it is not a theorem), which states that a probabilistic Turing machine can efficiently simulate any realistic model of computation. This thesis partially answers your question about the programming languages since almost all of them are "realistic".  

---

