使用constexpr进行计算是否具备图灵完备性？
我们知道C++模板元编程是图灵完备的，但预处理器元编程不是。 C++11为我们提供了一种新形式的元编程：constexpr函数的计算。这种形式的计算是否具有图灵完备性？我认为由于constexpr函数中允许递归和条件运算符（?:），所以它应该是具备的，但我希望有更多专业知识的人来确认。
左线性和右线性语法
我需要帮助构建以下语言的左线性和右线性文法？a) (0+1)*00(0+1)* b) 0*(1(0+1))* c) (((01+10)*11)*00)* 对于 a) 我有以下内容:Left-linear S --> B00 | S11 B --> B0|B1|011 Rig...
示例问题不属于P类问题也不属于NP完全问题，但属于NP问题。
我在大学里有一门叫做算法分析的课程，我们目前正在学习不同的复杂性类——P、NP、NP-hard等。 我们已经讨论了NP完全问题作为NP和NP-hard交集，并且包含在NP中的P问题。我们也谈到了一些例子，主要是NP完全问题（k着色、k团、SAT）。 大部分时间，我们通过以下方式证明一个问题...
图灵可判定和共图灵可判定的区别
我真的很难理解这两者之间的区别。从我的教材中，它基本上通过以下方式描述了它们之间的区别： 如果一门语言是图灵可识别语言的补集，则该语言为共同图灵可识别语言。 我猜我不理解这个定义的部分是：当它是一个图灵可识别语言的补集时，这意味着什么？ 你如何确定它是否是另一种语言的补集？
旅行商问题中NP-hard和NP-Complete的混淆
旅行推销员优化问题（TSP-OPT）是一个NP难问题，而旅行推销员问题（TSP）则是NP完全问题。然而，由于如果能在多项式时间内解决TSP问题，那么也能解决TSP-OPT问题，因此TSP-OPT可以被约化为TSP(1)。我原以为在A可以被约化为B的情况下，B必须和甚至比A更难。但是从下面的参考...
什么意思是lambda演算等同于图灵机
我试图理解λ演算及其与语言、编译器和二进制代码的关系。λ演算等价于图灵机，它到底意味着什么，它在哪里体现出来？ 我不明白λ演算如何取代图灵机成为计算理论模型。图灵机是关于按顺序执行指令以改变状态，而λ演算则是关于表达式求值得到某些东西。它更抽象，像是一种编程语言，而不是如何实际地计算某些东西...
递归语言和可递归枚举语言有什么区别？
我想知道递归语言和可递归语言在停机和图灵机方面的区别。 我知道可递归语言是递归语言的子集，但除此之外我不确定区别。 我想知道递归语言和可递归语言在停机和图灵机方面的区别。 可递归语言可以由图灵机接受并产生回答结果，而递归语言可以通过算法计算并得到结果。递归语言是可递归语言的超集，这意味着递归...
创建HTML quine是否可能？
根据标题，是否可以在HTML中创建一个（非平凡的）quine？ 我的HTML quine定义： 非平凡的HTML quine是指不为空且至少使用一个HTML标签的quine，假定HTML文件中的某个字符串被浏览器呈现为纯文本。HTML quine的定义是，q.html的输出由标准浏览器呈...
在字母表{0,1}上，对于{ w | w <> w^R }，它是否是一个上下文无关语言？
我非常希望您能够帮助我决定关于字母表 {0,1} 上的所有单词语言，即那些无法从两侧读取相同的单词，{w | w <> wR} 是否是一个上下文无关语言（也就是说，它可以转化为特定的文法规则）。 我试图通过泵引理证明它不是一个上下文无关语言，但我没有找到会导致矛盾的字符串。 有...