turing-machines - 图灵机需要多少个状态来决定这种语言？

Question

语言 L = {1^200}，或者更确切地说，连续有 200 个 1 的语言？Aka，这个 TM 只有在连续收到 200 个 '1' 时才接受。因此需要 200 个状态来解决这个问题，还是可以用更少的状态来简化？

我要求这个来帮助理解 TM 的工作原理。

注意：字母表只是 {1}。TM 可以使用任意数量的磁带。

Answer 1

使用两个磁带，或者一个磁带字母表（不同于输入字母表）比简单的 {1,blank} 大，可以做得更好。事实上，您唯一需要第二个磁带或扩展字母表的就是标记输入的开始和结束位置。

所以我们可以这样开始：遍历输入，每隔 1 擦除一次。同时，我们可以计算输入长度的奇偶校验。这只能通过两种状态来完成，称它们为 EVEN 和 ODD。以 EVEN 状态开始。当您读取 1 时，切换到 ODD 状态。在 ODD 状态下，当您读取 1 时，将其擦除并切换到 EVEN 状态。

然后使用另外两个状态返回做同样的事情。然后用另外两个状态第三次检查输入。此时，当其中一次扫描读取奇数个 1 时，您的机器要么拒绝，要么您现在有 1/8 的 1。

使用类似的结构，您可以遍历输入，从每 5 个 1 中擦除 4 个，并确保输入的长度是 5 的倍数。它可以在 5 个状态下完成。这样做两次。

现在，如果所有奇偶校验和（5-arity）检查都通过并且您只剩下一个 1，那么您的原始输入中有 1*5*5*2*2*2=200 个 1。否则不行。使用的状态总数：2+2+2+5+5=16（如果计算接受和拒绝状态，则为 18）。

更高级的结构可以在更少的状态下完成相同的任务，但您几乎可以保证运行时将是荒谬的，并且您需要一个至少为 {0,1,blank} 的磁带字母表。如果您真的想很好地了解图灵机的工作原理，请考虑该算法如何弥补图灵机缺乏随机存取存储器（以状态的形式）。你能为语言 {1^99} 做一个类似的算法吗？{1^97} 怎么样（提示：它可以在少于 97 个状态的情况下完成，但你需要一些新的聪明才智）？

Answer 2

我假设 L 只包含单个句子 1^200。然后，这一切都取决于您对字母的定义。如果将“1”定义为字母表，则需要 201 个状态，包括初始状态。如果您将字符串 1^200 定义为“字母表”，那么您只需要两个状态：初始状态和结束状态，并用标记为 1^200 的箭头连接。

Answer 3

对于确定性有限自动机，您需要像@sawa 所说的 201 个状态。但是，图灵机可能会保留一个计数器，然后将其与 200 进行比较，这可以用更少的状态来完成。所需的状态数取决于您的图灵机型号；多磁带机可能使用较少的状态，但单磁带机可能需要 201。