图灵机接受总理长度

我有一个要求我描述了接受L = {a^n: n is prime}非确定性图灵机程序的功课问题的字符串。我不确定如何去做这件事。我知道吗？我是否使用a作为一元数字并对它们进行计数？我可以忽略这个字符串，只是测试主要的n？或者是已知的主要值，因此只有那些单元格位置才能接受状态，并且我可以像正常一样读取数据？图灵机接受总理长度

我该怎么办？

来源

2012-04-12 calccrypto

你应该请你的讲师或导师澄清。我们可以尝试猜出它们的含义（不管这种猜测是否聪明），但只有他们知道。 – paxdiablo 2012-04-12 01:13:35

如果你的标题去的话，大概是什么的意思是，你的NTM应该接受最佳长度的'a's任何字符串。所以计算你的'a'，如果看到任何其他符号，并且没有更多符号时，拒绝字符串，如果计数是质数，则接受。看起来像。当然，没有素数是“已知的”，你的磁带最初只包含一系列'a's，其余的都是空白的。 – 2012-04-12 08:07:20

上http://programmers.stackexchange.com/ – Abizern 2012-09-23 20:25:48

你可以把埃拉托色尼的实际无限筛到您的原点的左侧，在磁带上。

不确定性，您可以为每个国家一个以上的转换规则。所以，当以n的增量进行离开时，您可以在每个点上a。继续向左走并以n为增量标记磁带;或b。从原点开始，下一个n。

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

因此，您的最初磁带，........aaaaaaa.........将最终变得像.c.ccccc.ccc.c.ccc.c.ccc[p]cpcpp.OaaaaaaaA...x.y.z...（与[]标记磁带上的最终头部位置）。

来源

2012-04-12 12:03:21

首先，你可以使用一个内存位置的某处以字符串标志是否已被发现是最佳长度与否，然后做更多或更少内斯建议是什么（虽然我真的不明白他的回答的全部）。

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

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

最后一个问题。字符串可能在之前被接受（尽管时间在这里是一种非概念），但它们被发现是非素数。如果你能弄清楚这个问题，你比我早一步。

P.S. Drineas是邪恶的

来源

2012-04-12 19:08:29 Outback

图灵机接受总理长度

回答

相关问题