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

Question

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

Answer 1

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

在此示例中，独特的状态由以下部分组成:

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

因为有σ可能的符号，这意味着h中的每一个每个 k 上的单元格磁带可以是 σ 之一可能的值。共有 hk所有磁带之间的单元，并且它们可以各自独立地是 σ 之一值(value)观。所以总共可能的组合是σ^(h*k) - 此地址为 (1)。该表达式的字面意思是(可能的字母符号的数量)^(最大单元数 * 磁带数)。

对于(2)，还有一个额外的 q对磁带单元的每个组合都有效的状态组合。这就给出了一个额外的因子 q达到理论最大值。

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

因此可能状态的总数是 q * σ^(h*k) * h^k 的乘积