computation-theory - 图灵机可以执行快速排序吗？

Question

据我所知，可以使图灵机执行在磁带上编码的指令的循环或迭代。这可以通过识别行分隔符并使图灵机返回直到达到特定的行分隔符计数(即在循环内)来完成。
但是，图灵机也可以执行递归程序吗？
有人可以描述这种图灵机的各种细节吗？
我想，如果递归可以由图灵机执行，那么快速排序也可以执行？

Answer 1

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

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

数据的维度 l 在此上下文中是相关的，因为您不能期望它们可以适合单个磁带单元(否则它们将是有限的，并且在有限范围内对元素进行排序是一个更简单的线性问题)。

一般来说，图灵机的问题在于交换两个单元格的内容需要与它们的距离成正比的时间。当您需要移动(或比较)长度为 l 的磁带的连续部分时，情况会更糟，因为在单个磁带机上，您需要在磁带上的两个位置之间来回移动 l 次。

有关更多引用，请参阅 Holger Petersen 于 2008 年撰写的“单带离线图灵机上的元素差异性和排序”。