可判定性问题
是否可以有一个 NFA 来决定实数？
Can there be an NFA that decides on real numbers ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
是否可以有一个 NFA 来决定实数？
Can there be an NFA that decides on real numbers ?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
不，不可以。不确定性有限自动机接受字符串作为输入。所有字符串的集合是可数的，因此小于实数的集合。因此，您甚至无法将任意实数编码为 NFA 的输入。
No, there can not. A nondeterministic finite automaton accepts a string of characters as input. The set of all strings is countable, and hence smaller than the set of real numbers. Therefore, you cannot even encode an arbitrary real number as input to the NFA.
没有。
实数小数点后可以有无限位数。这些数字中可能不存在系统（即，它们可能是由随机过程生成的）。在这种情况下，对这个数字序列的描述不可能比序列本身短得多。
现在取这样一个实数r。由于任何 NFA 都只有有限数量的状态并且可以有限地描述，因此仅接受实数 r 是不够的（否则这将与以下事实相矛盾：无法对r进行有限的描述）。
Nope.
A real number can have an infinite number of digits behind the decimal point. There may not be a system in those digits (i.e., they may be generated by a random process). In that case there cannot be a description of this sequence of digits that is significantly shorter than the sequence itself.
Now take such a real number r. Since any NFA has only a finite number of states and can be described finitely, it will be inadequate to accept only the real number r (for otherwise that would contradict the fact that there cannot be a finite description of r).