performance - 如何计算图灵机运行时间？

Question

我只是复习一下计算定理。我遇到了如下问题。
考虑具有q 状态的确定性k-tape 图灵机
和 σ 字母符号。假设这台图灵机在使用
每个磁带上最多 h 个单元格。最长运行时间是多少？
为什么答案是q X(σ^hk)X(h^k)？
σ^hk 和 h^k 是什么意思？谢谢!

Answer 1

关键的见解是，要让图灵机停止，它不能进入​​循环。由于图灵机在进入特定状态后将始终遵循相同的序列，因此如果它两次变为相同状态，我们就知道该机器陷入了无限循环并且永远不会完成。因此，理论上它可以运行的最大步数是机器可能的不同状态的最大数量，而不是两次完全相同的状态。

在这个例子中，一个独特的状态由:

1. 每个 k 磁带上的值(h 单元格的最大值)，
2. 机器的当前状态(q 种可能性中的 1 种)，
3. k 个机头的当前位置。

因为有 σ 个可能的符号，这意味着每个 k 磁带上的每个 h 单元格都可以是 σ 可能的值。所有磁带之间总共有 hk 个单元格，它们每个都可以独立为 σ 值之一。所以所有可能的组合是 σ^(h*k) - 这解决了 (1)。该表达式的字面意思是(可能的字母符号数)^(最大单元格数 * 磁带数)。

对于 (2)，还有一个附加的 q 状态组合，可以对磁带单元的每个组合生效。这为理论最大值提供了一个额外的因子 q。

对于 (3)，对于每个 k 磁带，每个机头也可以独立地位于 h 可能单元位置之一。这增加了 h^k 可能状态的另一个因素。

所以可能状态的总数是 q * σ^(h*k) * h^k