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 年撰写的“单带离线图灵机上的元素区别和分类”。

Answer 2

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