primes - 图灵机接受质数长度的字符串

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

9年前关闭。




Improve this question




我有一个家庭作业问题，要求我描述一个接受 L = {a^n: n is prime} 的非确定性图灵机的程序。 .我不确定如何解决这个问题。我知道吗？我是否使用 a s 作为一元数字并计算它们？我可以忽略字符串，只测试主要的 n 吗？或者素数是已知的，因此只有那些单元格位置接受状态，我可以像往常一样读入数据？

我应该怎么做？

Answer 1

首先，您可以在某处使用内存位置来标记是否发现字符串具有质数长度，然后或多或少地按照 Ness 的建议进行操作(尽管我并不完全理解他的回答)。

使用埃拉托色尼筛。从长度为2的辅助字符串开始，在输入字符串和辅助字符串中向右移动一个，当碰到辅助字符串的结束字符时回到辅助字符串的开头，直到碰到输入的结束字符字符串。这样就可以看到helper 字符串是否对输入字符串进行了分割。然后转到长度为 3 的辅助字符串并执行相同操作，依此类推。仅当没有任何辅助字符串长度除以输入字符串长度时，输入字符串长度才是素数。如果一个辅助字符串长度确实除以输入字符串长度，请使用您的标志内存插槽来显示这一点。并让算法检查标志内存插槽，如果它被标记，则中止所有处理，以便可以拒绝字符串。

现在，在迭代输入的任何时候都允许非确定性跳出内循环，以便机器可以开始测试下一个长度的辅助字符串。这样，从某种意义上说，所有长度的辅助字符串都将被同时测试，但是当您的标志槽被标记时，它们都会停止处理并拒绝该字符串。

最后一个问题。字符串之前可能会被接受(虽然时间在这里是一个非概念)，但它们被发现是非素数。如果你能解决这个问题，你就领先我一步了。

附言德里尼亚斯是邪恶的