可证明是否等于可判定？
在计算理论中，“可证明的”和“可决定的”这两个术语可以互换使用吗？它们的含义相同吗？ 例如，你经常会看到一个问题是否可证明被称为决策问题（Das Entscheidungsproblem）。
什么意思是lambda演算等同于图灵机
我试图理解λ演算及其与语言、编译器和二进制代码的关系。λ演算等价于图灵机，它到底意味着什么，它在哪里体现出来？ 我不明白λ演算如何取代图灵机成为计算理论模型。图灵机是关于按顺序执行指令以改变状态，而λ演算则是关于表达式求值得到某些东西。它更抽象，像是一种编程语言，而不是如何实际地计算某些东西...
左线性和右线性语法
我需要帮助构建以下语言的左线性和右线性文法？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...
GPU着色器是否具有图灵完备性？
我知道完整的GPU是计算的庞然大物 - 包括每一步计算和内存。因此，显然GPU可以计算我们想要的任何东西 - 它是图灵完备的。 我的问题是关于不同GPU上的单个着色器（“流处理器”/“CUDA核心”）： 它是图灵完备的吗？ 理论上，我是否可以使用单个着色器在任意输入上计算任意函数？ 我试图了...
使用constexpr进行计算是否具备图灵完备性？
我们知道C++模板元编程是图灵完备的，但预处理器元编程不是。 C++11为我们提供了一种新形式的元编程：constexpr函数的计算。这种形式的计算是否具有图灵完备性？我认为由于constexpr函数中允许递归和条件运算符（?:），所以它应该是具备的，但我希望有更多专业知识的人来确认。
需要正则表达式来表示有限状态自动机：1的个数为偶数且0的个数也为偶数。
我的问题可能与您听到的不同。 我是一个初学者，正在学习有限自动机。我在互联网上搜索，以找到以下给定机器的有限自动机的正则表达式。 有人能帮我编写上述机器的“有限自动机正则表达式”吗？ 任何帮助将不胜感激。
理解自动机中的识别器和决策器
我对机器识别和决定语言的含义感到有些困惑。我觉得我接近了定义，但并不完全正确。 当有人说图灵机 T 识别语言 L 时，意思是 L = { <A> | A is a DFA } 其中DFA表示确定性有限状态自动机 我的理解是，可以构建一个图灵机，对于任何类型的输入（字符串、...
旅行商问题中NP-hard和NP-Complete的混淆
旅行推销员优化问题（TSP-OPT）是一个NP难问题，而旅行推销员问题（TSP）则是NP完全问题。然而，由于如果能在多项式时间内解决TSP问题，那么也能解决TSP-OPT问题，因此TSP-OPT可以被约化为TSP(1)。我原以为在A可以被约化为B的情况下，B必须和甚至比A更难。但是从下面的参考...
图灵可判定和共图灵可判定的区别
我真的很难理解这两者之间的区别。从我的教材中，它基本上通过以下方式描述了它们之间的区别： 如果一门语言是图灵可识别语言的补集，则该语言为共同图灵可识别语言。 我猜我不理解这个定义的部分是：当它是一个图灵可识别语言的补集时，这意味着什么？ 你如何确定它是否是另一种语言的补集？
Datalog计算类？
Datalog并不是图灵完备的。 但是它的计算类别是什么呢？ 它是否等同于有限状态机或下推自动机(即上下文无关)...还是介于两者之间？