Can a Turing machine perform Quicksort?

B

2

6

As far as I know, a Turing machine can be made to execute loops or iterations of instructions encoded on a Tape. This can be done by identifying Line separators and making the Turing machine go back until a specific count of Line separators is reached (that is, inside the loop). But, can a Turing machine also execute a recursive program?

Can someone describe various details for such a Turing Machine?

I suppose, if recursion can be executed by a Turing machine, the Quicksort can also be performed?

Braden answered 10/4, 2015 at 16:48 Comment(0)

T

14

If the question is if a Turing Machine can execute a sorting algorithm, the answer is yes, since any computable function can be implemented on a Turing Machine. However, if the question is really about mimicking the structure of quicksort, preserving its complexity, the answer is not so trivial, and it also depends on the number of tapes.

Supposing to have n elements, each one of dimension l=k*log(n), it has been proved that the best sorting algorithm on a single tape Turing Machine has complexity O(n^2*log(n)), so, in this case the answer is no: you have nothing similar to a quicksort. On the other side, with three tapes, you may write merge-sort like algorithms running with complexity O(n*log(n)*l).

The dimension l of data is relevant in this context, since you cannot expect they can fit in a single tape cell (otherwise they would be finite, and sorting elements in a finite range is a simpler, linear problem).

In general, the problem with Turing machines is that exchanging the content of two cells takes a time proportional to their distance. Things are even worse when you need to move around (or compare) consecutive portions of the tape of lenght l, since on a single tape machine you need to move back and forth l times between the two locations on the tape.

See "Element distinctness and sorting on one-tape off-line turing machines" by Holger Petersen, 2008 for more references.

Recommended topics

Hot tags