-2
$\begingroup$

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.

$\endgroup$

closed as off-topic by Andrej Bauer, Aryeh, Gamow, Jan Johannsen, Emil Jeřábek supports Monica Jan 14 at 8:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Andrej Bauer, Aryeh, Gamow, Jan Johannsen, Emil Jeřábek supports Monica
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ 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. $\endgroup$ – Aryeh Jan 12 at 23:25
  • $\begingroup$ 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)$. $\endgroup$ – Andrej Bauer Jan 13 at 10:51
  • $\begingroup$ @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 $\endgroup$ – Bananach Jan 13 at 14:28
  • $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jan 13 at 18:44
  • $\begingroup$ @AndrejBauer Which close votes? Maybe I can't see them without more reputation? $\endgroup$ – Bananach Jan 13 at 19:18
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very interesting! Is there a reason then that it seems all commonly used programming languages seem to behave equal in terms of complexity? $\endgroup$ – Bananach Jan 13 at 6:32
  • $\begingroup$ 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.) $\endgroup$ – Sasho Nikolov Jan 13 at 16:15
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you extend your answer to include that very similar statement? I cannot find it following the link in your answer $\endgroup$ – Bananach Jan 13 at 6:31
  • $\begingroup$ 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". $\endgroup$ – knop Jan 14 at 23:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.