问题标签 [computability]

所以我之前做了一个问题，说：

对于我说{a^2n , b}的那个，因为这保证了一个类似aab或aabaab等的字符串。不知道如何处理我在标题中发布的那个。可能的解决方案可能是a^2n, b^2m它总是偶数，但也有 2 个奇数，比如a^n b^3m也总是偶数。我可以设置边界n>=m吗？

谢谢！

如果 p 是图灵机，则 L(p) = {x | p(x) = 是}。

A 是可计算的吗？证明你的答案。

所以我试图弄清楚如何解决这个问题，这是我想出的答案：

(i) 所以我们知道 A 是一个不平凡的问题，因为一些图灵机 L(p) 是有限状态，而一些图灵机 L(p) 不是有限状态。

(ii) 当给定任意 2 个等价的图灵机 p 和 q 时，A 尊重等价性。

因此，通过应用赖斯定理，我们可以看到 A 是不可计算的。

我的理解是，由于它不可计算，因此当答案为“是”或“否”时，它可能不会停止。这就是为什么它不能被共同递归枚举的原因，因为它不能保证它总是在“否”时停止。

对于家庭作业，我得到了以下语法：

我用 LL(1) 计算得很好。第一组是：

以下套装是：

当我制作解析表时，示例字符串“ab”解析得很好。但是，当我尝试使用 LR(1) 解析相同的语法时，我遇到了错误。

对于项目集 0，我得到以下信息：（ , 分隔前瞻终端）

如果你做表，你会清楚地看到项目集0中A和B之间存在reduce-reduce冲突。如果要求我解析字符串“ab”，解析器将不知道是否要减少我的空到A或减少到B。我做错了什么？我总是被告知 LR(1) 实际上可以解析比 LL(1) 更多的语法，那么这里有什么问题呢？如果有人可以帮助我，我将不胜感激，因为这让我发疯。谢谢

这是我在阅读停止问题、科拉茨猜想和科尔莫哥洛夫复杂性时突然想到的一个问题。我试图搜索类似的东西，但我无法找到一个特定的主题，可能是因为它没有太大的价值，或者它可能只是一个微不足道的问题。

为简单起见，我将给出三个程序/功能示例。

所以我的问题是，如果有一种方法可以形式化程序的长度（如用于描述它的位）以及程序使用的内部存储器，以确定决定所需的最小/最大时间/步数程序是终止还是永远运行。

例如，在第一个函数中，程序不会改变其内部存储器并在一些时间步后停止。
在第二个示例中，程序永远运行，但程序也不会改变其内部存储器。例如，如果我们考虑与程序 2 具有相同长度且不改变其状态的所有程序，我们是否不能确定步数的上限，如果超过该上限，我们可以得出结论，该程序永远不会终止？（如果不是为什么？）
在最后一个例子中，程序改变了它的状态（变量 i）。因此，在每一步，上限都可能发生变化。

[简而言之] Kolmogorov 复杂性提出了一种查找对象（例如一段文本）的（描述性）复杂性的方法。我想知道，给定描述程序使用的内存空间的正式方式（在运行时计算），我们是否可以计算最大步数，如果超过，我们可以知道该程序是否会终止或永远奔跑。

最后，我想向我推荐任何我认为有用的资源，并帮助我弄清楚我到底在寻找什么。
谢谢你。（对不起我的英语，不是我的母语。我希望我很清楚）

程序打印 n 个命题符号的真值表需要多长时间？

（符号：P1、P2、...、Pn）

似乎无法破解这个问题，不太确定如何计算这个实例。

我被告知要写一篇论文，作为对 Hewitt Actor-based 模型的评论，其中我必须包括：

a) Hewwit 演员模型定义（完成，解释“演员”如何工作；不允许共享内存等）。

b) 微积分示例 => 如果我应该研究 Gul Agha 在 2004 年定义的 lambda 微积分、pi 微积分甚至 A-pi 微积分，我没有任何线索。

c) 可计算函数的定义 => 没有线索。据我所知，可计算函数被定义为图灵可计算的函数；但同时我读到 Actor-model 是图灵模型的改进；从某种意义上说，图灵机无法计算参与者的相关函数，因为它们没有界限。

d) 描述与其他计算模型的关系（简单，Actor 模型与图灵模型，我有）。

一些与 b) 和 c) 相关的说明，我可以扩展这些部分。一些网站、论文或解释将不胜感激。

已知存在可判定问题、半可判定问题和不可判定问题。TM（图灵机）接受的语言是一个 re set（递归可枚举），并且在某些情况下也是一个递归集。re（但不是递归）集合的一个例子是接受某个（固定）字符串“x”的 TM 集合。解释是这样的：“这个问题是半可判定的（即集合是 re），因为如果某个 TM_i（i 是它在哥德尔枚举中的索引）属于集合，那么通过算法（过程， TM, ecc.) 列出所有接受“x”的 TM，并继续这样做，在某个点我将能够找到 TM_i。但是，如果 TM_i 不属于该集合，那么我无法得出任何结论：列出所有接受“x”的 TM 的算法将永远持续下去。

现在我试着从不同的角度思考同样的问题。假设我有一个随机图灵机 TM_j，我想确定它是否属于上述集合。我可以将字符串“x”作为输入给 TM_j，如果它在“接受”状态（最终状态）停止，那么我知道 TM_j 接受“x”，因此是集合的一部分。另一方面，如果 TM_j 不接受“x”，它可能会停止在某个非最终状态（因此我知道 TM_j 拒绝“x”），或者它可能会永远循环下去。在第二种情况下，我不能通过观察两个相同的配置来列出 TM 在执行期间的所有配置并得出结论它永远循环（因此拒绝“x”）吗？如果“c1, c2, c3, c4, . . . , c21, c3, . . 。” 是 TM_j 的配置列表，我观察到 c3 是重复的，并且由于机器是确定性的，c3 后面会跟着 c4，c4 依次给出 c5，依此类推，直到 c21，然后又是 c3。. . 因此，我可以得出结论，TM_j 循环，因此“x”不能被它接受，因为它永远不会达到最终（接受）状态。然而，这意味着给定一个通用的 TM，我可以确定它是否属于该集合，因此该集合是递归的而不是递归可枚举的！

有人可以帮助我了解我的错误在哪里吗？

为了传达 Lambda 演算的优点，甚至 JavaScript 实现此类（图灵完备）公式的能力，我希望看到一个 JS 文件可以打印以下语言的正确字符串的最优雅和简洁的方式，给定一个自然数 n（从零开始）：

一个_n b _n c _n

这也意味着不使用外部库，也不使用迭代机制（例如“while”、“for”等）。

例如a _n b _n，作为一个上下文无关的语法可能不会比以下更简单：

function print(n) {if(n>0) {console.log('a'); print(n--); console.log('b');}}

可计算问题的特征是：

• 完整意味着它涵盖了所有情况；
• 机械意味着它是精确的；
• 确定性意味着如果输入相同的输入，将提供相同的输出。

如果我错了，请纠正我，我通过研究发现除了确定性之外并不完全知道它的实际含义。

所以，我试图证明一个简单的代码，例如：

是可计算的。

我知道如何表明它是确定性的，因为它相当明显，但我不确定如何表明它是mechanistic或complete。

Complete特性，据我了解，它更像是“代码是否有任何方式无法执行或作为错误返回？” 例如打开一个文本文件有可能文件不存在，因为输入了错误的文件名或输入了错误的位置等。

但是在上面的代码片段的情况下，我应该如何证明它是完整的？

至于机制“是否 1 + 1 = 2 而不是 3？”。

同样的事情，对于上面的代码片段，我如何证明它是精确的，因为代码本身并没有解决任何问题，它只是根据 n 值打印“hello”？在这种情况下，n^2 + n 个“你好”。