turing-machines - 可判定性问题

Question

可以有一个 NFA 决定实数吗？

Answer 1

不，不能。非确定性有限自动机接受字符串作为输入。所有字符串的集合都是可数的，因此小于实数集合。因此，您甚至不能将任意实数编码为 NFA 的输入。

Answer 2

没有。

实数的小数点后面可以有无限位数。这些数字中可能没有系统（即，它们可能是由随机过程生成的）。在那种情况下，这个数字序列的描述不能比序列本身短得多。

现在取这样一个实数r。由于任何 NFA 都只有有限数量的状态并且可以被有限地描述，因此仅接受实数r是不够的（否则这将与不能有r的有限描述的事实相矛盾）。