问题标签 [decidable]

我的问题：定义两个单词集合 P 和 Q（即两个问题）使得：P 不可判定且不可半可判定，Q 不可判定且可半可判定且 P ⊂ Q

谁能给我一个证明，证明 K-Complexity 是无法使用约简解决的。

例如：

PCP(2) <= PCP(3)

我可以通过简化为 PCP(2)（通过映射每个实例）来证明 PCP(3) 是不可解的。

我不确定如何将 K-Complexity 减少为另一个已知的不可判定问题（如停止问题）。即，X <= K-复杂度

你能给我证明吗？至少给我一些想法（X）。

提前致谢

我一直在阅读，并且试图了解在修整机方面的减少。这就是我的理解：这意味着它将问题 A 简化为问题 C。但我不太确定它是如何工作的。让我们看一个例子：

给定语言 L：

使用归约如何证明Atm < L.

我的解决方案：

M 是一个图灵机，它接受任何字符串并在该字符串上停止。D 是 DFA hast 接受语言 L 及其等效于 TM M。 Atm 是一个 TM, M 接受字符串w。

你怎么能证明使用直接减少Atm < L??

这是我的第一篇文章，如有错误请见谅。

我怀疑，在 Coq 中，像 Stream 这样的协约类型没有可判定的相等性。也就是说，给定两个流 s 和 t，不可能确定是 s=t 还是 ~(s=t)。我怀疑 Coq 中的所有共归纳类型都是如此。

通过堆栈交换快速谷歌和搜索不会显示任何确认。任何人都可以确认或纠正我吗？

如何使用缩减方法证明语言的长度除以 2？L={ | 是一个图灵机，其中 |L(M)|= 0 mod 2}

我有 2 个想法，但我害怕遵循错误的想法 1）我使用 Amt 的归约方法，我说图灵机将 x=w0.....wi 作为输入并接受当且仅当 wi = 0 模 2 。

2）我用NOT HALT的归约法，我说图灵机会拒绝任何输入，所以图灵机的长度为0，满足上面的条件！

有什么建议吗？

假设我在 Agda 中有这个 Subset 的定义

我有一套

是否有可能证明 q 的所有子集都是可判定的，为什么？

Decidable 在这里定义：

我正在阅读 Mozilla 的 Javascript 教程，我通过了这条信息。

高级语言嵌入了一个叫做“垃圾收集器”的软件，它的工作是跟踪内存分配和使用，以便找到何时不再需要分配的内存，在这种情况下，它会自动释放它。这个过程是一个近似值，因为知道是否需要某块内存的一般问题是无法确定的（不能通过算法解决）。

我熟悉不可判定性和垃圾收集器的概念，但我似乎无法理解为什么这是一个不可判定的问题？

Z3（版本 4.4.1）报告我正在编写的工具生成的许多查询“未知”，我已将问题缩小到使用(_ as-array ...)：

我是否陷入了一个已知无法确定（或在 Z3 中未实现）的案例？

你好。我正在创建一个算法来显示 L2 以上是可判定的。提示如下：

为了证明 L2 是可判定的，在所有长度不超过 10 的输入字符串上测试给定的 TM M，每个字符串执行 10 步。请注意，要测试的此类字符串数量有限，因此该算法将始终终止。如果 M 在 10 步内停止在任何输入字符串 w 上，则令 w' 是长度为 10 的 w 的前缀。M 也会在 10 步内停止输入 w'，因此上述决策算法会找到它。

我只是无法理解这个提示。

正如你在上面看到的我所做的算法，我不知道从上面的那些 L2 定义和提示中做出正确的算法。

我需要正确编写它的帮助（请使用您编写算法的风格。如果主要思想是正确的，我认为风格并不重要。我不明白的是它的想法。）

如果你能帮助我，非常感谢。

所以我正在查看我的笔记以解决这个问题，我似乎无法理解这个问题是如何工作的。假设我们有 M，并且 M 接受一个使其访问每个非停止状态的输入。

我说服自己这个问题是可以判定的，但我很难证明这一点。我的答案的粗略概述是：假设我们有一个只有一个停止状态的 TM T，如果它想要通过所有状态，它需要通过这个停止状态，我们需要以某种方式显示它们如何循环通过所有的州都是这样。

任何帮助都会有所帮助，谢谢！