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

Improve this question
$\endgroup$
6
  • 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, 2019 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, 2019 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, 2019 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, 2019 at 18:44
  • $\begingroup$ @AndrejBauer Which close votes? Maybe I can't see them without more reputation? $\endgroup$
    – Bananach
    Jan 13, 2019 at 19:18

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2019 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, 2019 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.

Improve this answer
$\endgroup$
2
  • $\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, 2019 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, 2019 at 23:54

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