图灵机可以执行Quicksort吗？

Question

据我所知，可以使图灵机执行在磁带上编码的指令的循环或迭代。这可以通过确定行分隔符并使Turing机器返回直到达到行分隔符的特定计数（即在循环内部）来完成。但是，图灵机还能执行递归程序吗？

有人可以描述这种图灵机的各种细节吗？

我想，如果可以通过图灵机执行递归，那么还可以执行Quicksort吗？

Answer 1

如果问题是图灵机是否可以执行排序算法，答案是肯定的，因为任何可计算的功能都可以在图灵机上实现。但是，如果问题实际上是关于模仿快速排序的结构，保持其复杂性，那么答案并不是那么简单，它还取决于磁带的数量。

假设有n个元素，每个元素的维数为l = k * log（n），则已证明在单个磁带图灵机上的最佳排序算法的复杂度为O（n ^ 2 * log（n）），因此，在这种情况下，答案是否定的：您没有类似于快速排序的东西。另一方面，使用三盘磁带，您可以编写类似合并排序的算法，算法的复杂度为O（n * log（n）* l）。

数据的维数l在这种情况下是相关的，因为您不能期望它们可以容纳在单个磁带单元中（否则它们将是有限的，并且在有限范围内对元素进行排序是一个更简单的线性问题）。

通常，图灵机的问题在于交换两个单元格的内容所花费的时间与它们的距离成正比。当您需要移动（或比较）长度为1的磁带的连续部分时，情况甚至更糟，因为在一台磁带机上，您需要在磁带的两个位置之间来回移动l次。

有关更多参考，请参见Holger Petersen的“单带离线图灵机上的元素区别和分类”，2008年。

Answer 2

是的，图灵机可以执行任何算法，包括快速排序。