是否可以设计一个接受无理数的自动机？
Is it possible to design an automaton that accepts irrational number?
给定一个有理数，是否可以知道该数的根或其他幂是否为无理数？可以为此目的设计自动机吗？
无理数是一个无穷大的字符串，如果你想要一个可以读取它的自动机，它就需要无限地继续读取。
你不能建立一个决策者（一个总是停止并输出真或假的机器），但你可以建立一个接受者（一个停止并输出假，但永远持续为真的机器），这就是我相信你正在问。
考虑一台接受无理数形式
的机器
0.10110111011110111110...
1s 的运行长度总是在 0s 之间增长。定义一个可以接受这个数字的图灵机相对容易。
（对于这种机器的实现，我建议 The Annotated Turing，它也有一个接受 √2 的机器的实现。）
给定一个有理数，是否可以知道该数的根或其他幂是否为无理数？可以为此目的设计自动机吗？
无理数是一个无穷大的字符串，如果你想要一个可以读取它的自动机，它就需要无限地继续读取。
你不能建立一个决策者（一个总是停止并输出真或假的机器），但你可以建立一个接受者（一个停止并输出假，但永远持续为真的机器），这就是我相信你正在问。
考虑一台接受无理数形式
的机器0.10110111011110111110...
1s 的运行长度总是在 0s 之间增长。定义一个可以接受这个数字的图灵机相对容易。
（对于这种机器的实现，我建议 The Annotated Turing，它也有一个接受 √2 的机器的实现。）