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

Question

我有一个作业问题，要求我描述一个接受L = {a^n: n is prime}. 我不知道该怎么做。我知道吗？我是否使用as 作为一元数字并计算它们？我可以忽略字符串，只测试 n 的主要部分吗？或者是已知的素数，因此只有那些单元格位置是接受状态，我可以像正常一样读取数据？

我该怎么办？

Answer 1

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

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

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

最后一个问题。字符串可能在被发现之前被接受（尽管时间在这里不是一个概念）它们被发现是非质数。如果你能解决这个问题，你就比我领先一步。

PS Drineas 是邪恶的

Answer 2

您可以在磁带上将实际无限的 Eratosthenes 筛放在起点的左侧。

非确定性允许您为每个状态拥有多个转换规则。因此，当以 为增量向左移动时n，您可以在每个点a. 继续向左标记磁带，增量为n; 或b。从原点重新开始，下一个n。

然后让你的起始状态有两条规则（也许在检查你在磁带上得到的所有a东西都只有 s 之后）：开始标记 2 的倍数，然后b。（现在假设筛子已经到位）计算你a的 s 并使用原点左侧标记的素数来决定是否接受。

因此，您的初始磁带........aaaaaaa.........最终会变成类似.c.ccccc.ccc.c.ccc.c.ccc[p]cpcpp.OaaaaaaaA...x.y.z...（[]在磁带上标记最终磁头位置）。