time-complexity - 存储程序计算机的复杂性降低

Question

图灵机上的维基百科页面指出，通用图灵机比它模拟的机器慢最多一个日志因子。我很好奇 - 现实生活中的等价物是什么，比较纯硬件解决方案（非存储程序计算机 - 例如 ASIC）与存储程序计算机？它也是一个日志因素吗？

Answer 1

维基百科页面有点谨慎。事实上，您可以为一台磁带机编写一台通用磁带机，而无需任何开销。我不知道确切的参考，但结果不知何故属于该主题的民间传说。关于具有次二次复杂度的程序的模拟，只有一个小的“灰色”区域。这与通用机器可能需要在开始模拟之前重新调整输入的事实有关，并且这样的操作在单个磁带机器上可能已经花费了二次时间。

这在某种程度上与单磁带机上的元组编码的一般问题有关，据我所知，这在某种程度上被忽略了，而它是复杂性问题的核心。

目前，我个人的感觉是，你可以克服二次复杂度机器的模拟问题，得到一个真正公平的通用机器。