给定一个有理数，是否有可能知道该数的根或其他幂是否是无理数？可以为此目的设计自动机吗？
最佳答案
无理数是一个无限的字符串，如果你想要一个可以读取它的自动机，它需要继续无限地读取。
你不能构建一个决策器(一台总是在输出 true 或 false 时停止的机器)，但你可以构建一个接受器(一台因 false 停止，但永远为 true 继续运行的机器)，这就是我相信你的询问。
考虑一台接受无理数形式的机器
0.10110111011110111110...
1 的运行长度始终在 0 之间增长。定义可以接受这个数字的图灵机相对容易。
(对于这样一台机器的实现，我建议 The Annotated Turing ，它也有一个接受 √2 的机器的实现。)
关于math - 是否有可能设计一个接受无理数的自动机？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34818529/