2

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

4

2 回答 2

4

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

在此示例中，唯一状态由以下各项组成：

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

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

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

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

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

于 2013-11-04T04:31:20.813 回答
1

将您的图灵机想象成一个线性有界自动机 (LBA)，它在 h*k 的范围内工作。让我们首先考虑单磁带机。

对于单个磁带 LBA，如果 LBA 具有：

1)q状态 2)g磁带字母表中的符号，以及 3) 长度的输入n，

那么它可能的配置数量是q * n * g^n针对单个磁带 LBA 的。 LBA 停止问题的证明

简单地说，对于单个磁带 LBA，我们有g^n可能的磁带，并且n磁头可能指向的位置以及q机器可能处于的状态。因此我们有q * n * g^n配置。

为了将其推广到 k-tape 机器，有(g^n)^k可能的磁带配置。所有磁头都有n ^ k可能的配置（因为您可以同时移动一些或所有磁头），并q说明机器可能处于其中。因此，不同配置的数量将是q * (n ^ k) * g^(nk)

更改n为 your h，这实际上是单个磁带 LBA 的长度，更改为gyour σ，就有了答案。

于 2013-11-04T04:37:21.253 回答