图灵机需要多少个状态来决定这种语言？
语言 L = {1^200}，或者更确切地说，是连续有 200 个 1 的语言？也就是说，该 TM 仅在连续接收到 200 个“1”后才接受。因此是否需要 200 个状态来解决这个问题，或者可以用更少的状态来简化这个问题？
我问这个是为了帮助理解 TM 的工作原理。
注意：字母表就是 {1}。 TM 可以使用任意数量的磁带。
The language L = {1^200}, or rather, the language such that there are 200 1's in a row? Aka, this TM only accepts once it receives 200 '1's in a row. Would it therefore need 200 states to solve this, or could this be simplified with less states?
I'm asking this to help understand how TM's work.
note: The alphabet would be just {1}. The TM can use as many tapes as you'd like.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我假设 L 仅包含单个句子 1^200。然后，这完全取决于您对字母表的定义。如果将“1”定义为字母表，则需要 201 个状态（包括初始状态）。如果您将字符串 1^200 定义为“字母表”，那么您只需要两个状态：初始状态和结束状态，并用标记为 1^200 的箭头连接。
I assume L only contains the single sentence 1^200. Then, it all depends on what you define as the alphabet. If you define '1' as an alphabet, you need 201 states including the initial state. If you defined the string 1^200 as an 'alphabet', then you only need two states: the initial state and the end state, connected with an arrow labeled 1^200.
对于确定性有限自动机，您需要像 @sawa 所说的 201 个状态。然而，图灵机也许能够保留一个计数器，然后将其与 200 个进行比较，这可以用更少的状态来完成。所需的状态数量取决于您的图灵机模型；多磁带机可能使用更少的状态，但单磁带机可能需要 201 个状态。
For a deterministic finite automaton, you would need 201 states like @sawa said. However, a Turing machine might be able to keep a counter and then compare it against 200, which could be done with fewer states. The number of states required depends on your Turing machine model; a multi-tape machine could probably use fewer states, but a one-tape machine will probably require 201.
使用两盘磁带或一个比简单的 {1,blank} 大的磁带字母表（不同于输入字母表），可以做得更好。事实上，您唯一需要第二个磁带或扩展字母表的用途是标记输入的开头和结尾。
所以我们可以如下开始：遍历输入，每隔一个擦除1。同时，我们可以计算输入长度的奇偶校验。这只需两个状态即可完成，称为偶数和奇数。从偶数状态开始。当读取到1时，切换到ODD状态。在 ODD 状态下，当读到 1 时，将其擦除并切换到 EVEN 状态。
然后返回使用另外两个状态做同样的事情。然后用另外两个状态第三次检查输入。此时，要么当其中一次扫描读取奇数个 1 时您的机器已拒绝，要么您现在拥有 1/8 数量的 1。
使用类似的结构，您可以遍历输入，擦除每 5 个 1 中的 4 个，并确保输入的长度是 5 的倍数。它可以通过 5 个状态来完成。这样做两次。
现在，如果所有奇偶校验和（5 元数）检查都通过，并且您只剩下一个 1，那么您的原始输入中有 1*5*5*2*2*2=200 个 1。否则不会。使用的总状态：2+2+2+5+5=16（如果算上接受和拒绝状态，则为 18）。
更奇特的结构可以在更少的状态下完成相同的任务，但几乎可以保证运行时间会很荒谬，并且您将需要至少为 {0,1,blank} 的磁带字母表。如果您确实想很好地了解图灵机的工作原理，请考虑该算法如何弥补图灵机缺乏随机存取存储器（以状态的形式）。你能为语言 {1^99} 制作一个类似的算法吗？那么 {1^97} 怎么样（提示：可以用少于 97 个状态来完成，但您需要一些新的技巧）？
With two tapes, or a tape alphabet (different from the input alphabet) larger than simply {1,blank}, one can do much better. In fact, the only thing that you need the second tape or extended alphabet for is marking where the beginning and end of the input are.
So we can begin as follows: run over the input erasing every other 1. Simultaneously, we can count the parity of the length of the input. This can be done with only two states, call them EVEN and ODD. Start in the EVEN state. When you read a 1, switch to the ODD state. In the ODD state, when you read a 1, erase it and switch to the EVEN state.
Then go back doing the same thing using two more states. Then go over the input a third time with two more states. At this point, either your machine has rejected when one of the sweeps read an odd number of 1's, or else you now have 1/8th as many 1's.
Using a similar construction, you can run over the input erasing 4 out of every 5 1's and making sure the length of the input is a multiple of 5. It can be done with 5 states. Do that twice.
Now, if all the parity and (5-arity) checks pass and you are left with a single 1, then your original input had 1*5*5*2*2*2=200 1's in it. Otherwise not. Total states used: 2+2+2+5+5=16 (or 18 if you count your accept and reject states).
Fancier constructions can do the same task in fewer states, but you are pretty much guaranteed that the runtimes will be ridiculous and you will need a tape alphabet of at least {0,1,blank}. If you really want to get a good handle on how Turing Machines work, think about how the algorithm makes up for the Turing Machine's lack of random access memory (in the form of states). Could you make a similar algorithm for the language {1^99}? What about {1^97} (hint: it can be done with fewer than 97 states, but you'll need some new cleverness)?