cal*_*pto 4 primes turing-machines primality-test
我有一个家庭作业问题要求我描述一个接受的非确定性图灵机的程序L = {a^n: n is prime}.我不知道如何解决这个问题.我知道吗？我使用as作为一元数字并计算它们吗？我可以忽略字符串,只测试n的主要部分吗？或者是已知的主要值,因此只有那些单元格位置接受状态,我可以像正常一样读取数据？
我该怎么办呢？
首先,你可以在某个地方使用一个内存位置来标记字符串是否已被发现是否为长度,然后或多或少地做出Ness所建议的内容(尽管我并不完全理解他的答案).
使用Eratosthenes的Sieve.从长度为2的辅助字符串开始,并在输入字符串和辅助字符串中向右移动一个,当您点击辅助字符串的结束字符时返回辅助字符串的开头,直到您点击输入的结束字符串.通过这种方式,您可以看到辅助字符串是否划分输入字符串.然后转到长度为3的辅助字符串并执行相同操作,依此类推.只有当没有辅助字符串长度除以输入字符串长度时,才输入字符串长度为prime.如果一个辅助字符串长度除以输入字符串长度,请使用标记内存插槽来显示.并让算法检查标志内存槽,如果它被标记,则中止所有处理,以便可以拒绝该字符串.
现在,在迭代输入时的任何时刻都允许从内循环中跳出非确定性,因此机器可以开始测试下一个长度的辅助字符串.这样,从某种意义上说,所有长度的辅助字符串都将同时进行测试,但是当标记槽标记时,它们都会停止处理并拒绝字符串.
最后一个问题.字符串可能会接受前(虽然时间排序是非概念在这里的),他们被发现有非黄金.如果你能解决这个问题,那么你就领先于我.
PS Drineas是邪恶的