问题标签 [computation-theory]

我真的很喜欢你的帮助来决定字母表上所有单词的语言是否{0,1}不能以相同的方式从两边读取，是否是一种上下文无关的语言（也就是说，它可以转换为特定的语法规则）。{ w | w <> wR }

我试图通过泵引理证明它不是上下文无关语言，但我没有找到会导致我矛盾的字符串。

有什么建议么？

我真的很难理解这两者之间的区别。从我的教科书中，它基本上通过说来描述差异

如果一种语言是图灵可识别语言的补充，则它是共同图灵可识别的。

我想我不明白这个定义的一部分是：当它是图灵可识别语言的补充时，它意味着什么？

您如何确定它是否是另一种语言的补充？

在 Milner 的 Pi 演算中，当多个进程从同一个通道读取时，评估语义是什么？

规则说

!x(a). P | ?x(b) Q ~> P | Q[a/b]

但是像这样的情况呢

!x(a). P | ?x(b) Q | ?x(c) R

?

只要研究那篇著名的论文PRIMES is in P，就会感到困惑。

所提出算法的第一步是If (n=a^b for nature number a and b>1), output COMPOSITE.由于整个算法在多项式时间内运行，因此这一步也必须在 O((log n)^c) 内完成（给定输入大小为 O(log n)。但是，我无法弄清楚谷歌搜索后命中目标的任何算法。

问题：

是否有任何算法可用于测试多项式时间内某个其他数字的指数是否为指数？

谢谢和最好的问候！

上下文无关语言集合的联合总是上下文无关的吗？证明你的答案......

我知道答案是肯定的，但我该如何证明呢？

我需要在 C++ 中设计一个图灵机模拟器，它接受一个输入文件，如下所示：

Q:q1,q2,q3,q4
A:0,1
Z:0,1,x
T:q1,0,q2,x,R
T:q1,1,q2,x,R
T:q2,0,q2 ,0,R
...
S:q1
F:q3,q4

其中 Q 是状态，A 是输入值，Z 是磁带字母表，S 是开始状态，F 是接受和拒绝状态。

它需要处理一个输入，其中包含输入数量、输入字符串以及接受或拒绝。

所以如果输入的是：
3
0,#,1,1
1,1
0,1,0

输出将打印出步骤以及它是接受还是拒绝。

我需要创建一个执行算术运算的 TM，一个执行字符串运算的 TM，以及我选择的另一个。

任何有关如何开始的帮助表示赞赏。

我擅长算法，但不如转换实时问题并彻底学习它们以使其成为算法。我想知道是否有任何书籍/论文可以教授或让您揭开情况的神秘面纱并将其制定为算法。（这很像训练你打破局面并快速提出算法的心理能力。）

展示了一些解决这些问题的方法。任何简单的学习链接/材料都会对我有很大帮助。

注意：我知道 SO 不允许征求意见或含糊不清的东西（我不介意我的 Q 被降级）。但我在问一些具体的问题，希望能从这里的一些伟大的头脑中得到一些很好的信息。

如果我们主要使用上下文无关语言进行编码，我真的无法理解如何模拟图灵机（它接受递归可枚举语言）的输出。

相关问题：

• 将数字列表划分为2个相等总和列表的算法
• 将列表分成两部分，它们的总和彼此最接近

假设我有一个列表，其中包含确切的2k元素。现在，我愿意将它分成两部分，其中每个部分的长度为 ，k同时试图使各部分的总和尽可能相等。

快速示例： [3, 4, 4, 1, 2, 1]可能会拆分为[1, 4, 3] and [1, 2, 4]，总和差将是1

现在 - 如果部分可以有任意长度，这是分区问题的变体，我们知道这是弱NP-Complete.

但是关于将列表分成相等部分的限制（假设它总是kand 2k）是否使这个问题可以在多项式时间内解决？任何证明（或证明它仍然存在的证明方案NP）？

在模板元编程中，如果递归被错误地实现并导致无限循环，语言编译器可以检测到它吗？还是编译器会遇到最终的堆栈溢出和崩溃？我敢打赌，编译器无法检测到这一点，因为这样做会违反停止问题的不可判定性。

我的结论正确吗？当然我可以用一段代码来试试这个，但我想在这种情况下听到更多合格的想法。

编辑：谢谢大家，我大致知道我对 tmp 计算理论方面的推断没有错。我也明白编译器实现可以有任意的递归深度限制（当然我重申我可以测试第二部分，但这只是我的观点）。