小贝子编程

你能制作一个DFA / NFA / Lambda NFA来确定一个数字是否是素数吗?



正如标题所说，这可能吗？

不，这是不可能的。有几种方法可以将"所有素数的集合"编码为一种语言，并且这样做的标准方法(以二进制写出数字，写出等于数字的数字等(是不规则的。

正式证明这一点有点棘手，但使用常规语言的抽水引理或Myhill-Nerode定理是可行的。争论的关键归结为这样一个事实，即重复复制质数的一部分最终会给你一个非素数，这就是证明的技术细节所在。

希望这有帮助！

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium