问题标签 [computation-theory]

所以我正在学习用汇编语言为与URM Machine非常相似的抽象机器编程。URM 机器有 3 条基本指令（或某些文献中的 4 条）：
将寄存器归零：Z(r)
递增寄存器：S(r)
如果寄存器 r1 和 r2 包含相同的值，则跳转到一行或标号： J(r1,r2,l)
现在，我的抽象机器更弱，因为跳转它只允许寄存器和文字 0 之间的比较。
为了补偿它允许为寄存器分配任何值（不仅仅是零，如URM）和基本算术运算。
两台机器都允许无限数量的寄存器。

我能够编写一个成功比较两个正数并返回最大值的程序。
现在我想让我的程序也能够接收负数。

我的问题：如何检查数字是否为负数？甚至可以仅使用这些说明吗？

我承认我对这种低级语言不是很聪明......

我的最大程序如下：（输入在 r1 和 r2 上，输出在 r3 上）

谢谢！

在计算理论中，Provable 和 Decidable 这两个术语可以互换吗？他们的意思是一样的吗？

例如，您经常看到某事物是否可证明的问题称为决策问题 (Das Entscheidungsproblem)。

如果 TM 识别语言并进入接受或拒绝状态，则语言是可判定的。作为开发者。我认为这很重要，因为这意味着我们可以确定程序是否包含缓冲区溢出或死锁。此外，以下问题是不可判定的：

• 程序是否曾经访问过未初始化的变量。
• 两个上下文无关语法是否描述相同的语言。
• 如果子例程的参数是通过引用传递还是通过复制结果传递，是否会有所不同？

就可判定性而言，您会说什么是可判定性的关键点以及为什么可判定性很重要（尤其是对开发人员而言）。

注意：要点在答案中很好 - 我可以自己查找主题。我只是想知道要点是什么。

我需要证明 A 不是上下文无关的。我猜我必须为此使用 Pumping Lemma，但是如何？

是否有一种算法可以从给定的上下文无关语法生成所有字符串？

Σ 从 i=1 到 n of(n)(n+1)/2

给定 n 的计算上限是多少？是 O(n^3) O(n^2) 吗？

例子：

等等，那么作为 N 的函数，这个计算的上限是多少？是吗 ：

O(n^3)?

如果有人能够向我解释 Kolmogorov 复杂性如何与随机性和随机输入相关，我将不胜感激。

我无法理解的另一件事 - 我们知道计算给定输入 X 的 Kolmogorov 复杂度是不可确定的。鉴于此，它如何成为随机性的衡量标准？

谢谢

我只是在看图灵机模拟器代码并遇到以下语句

“磁带将时间和位置映射到符号。要计算符号，我们必须提前一步查看机器。如果当时磁头在请求的位置，符号已根据表格根据表发生变化，具体取决于相同位置的前一个符号和机器所处的状态。否则，符号没有改变。

斜体部分是什么意思？在这种情况下，请求的位置是什么意思？

我在大学有一门叫做算法分析的课程，我们目前正在学习不同的复杂性类别——P、NP、NP-hard 等。

我们已经讨论了作为 NP 和 NP-hard 的交集的 NP 完全问题，以及 NP 中包含的 P 问题。我们还讨论了一些示例，主要是 NP 完全问题（k-coloring、k-clique、SAT）。

大多数时候，我们通过以下方式证明问题是 NP 完全的：

一种。找到一个不确定的算法来解决它（使用选择、成功、失败）；

湾。将一个已知的 NP 完全问题简化为它。

问题是，当这些问题在确定性机器上运行时（顺序地，而不是在遇到选择时同时分支）具有指数时间的解决方案。

我的问题是——我从来没有遇到过在多项式时间内和指数时间内都无法解决的问题；多项式时间问题属于 P，而指数时间问题通常属于 NP 完全问题。

这里有一个有用的维恩图： http ://en.wikipedia.org/wiki/Np_complete

1. 我想知道一个问题的例子，它既不在 P 中，也不在 NP-complete 中，但在 NP 中。

2. 此外，本质上是指数问题，例如生成一组 NP 完全的幂集吗？还是该名称仅适用于仅使用指数时间算法的问题，因为没有其他明显的方法可以解决它？

好的，所以我给了Rosh Oxymoron的答案，因为他实际上列出了一些疑似 P 和 NPC 之间问题的例子。感谢你们的帮助，我实际上注意到我把这个问题放在了错误的地方。还有： https ://cstheory.stackexchange.com/

我在其中找到了以下对我的问题非常有用的答案 ： https ://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc 专门针对我的问题，以及： https://cstheory .stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np 如果与最初的问题不完全相关，这通常很有趣。

非常感谢，

担

我对以下语言有疑问：

我必须写一个上下文无关的语法：

它描述了它。我已经做了一些练习，但这对我来说真的很难。我坐了几个小时没有一个有用的方法。如果没有N0: (m=l) v (l = 2n)部分，编写语法不会有问题 。但我不知道如何完成这个。我会非常感谢任何建议。