问题标签 [decidable]

在以下算法中：

我们使用图灵机实现了一个枚举器，枚举器应该输出图灵机接受的语言。来自 Σ* 的接受词被打印多次（每次迭代之前打印的词将被再次打印）。

为什么我们不能只说 - “对 Σ* 中的每个单词运行 M。如果它接受则打印，如果拒绝则继续下一个单词”。然后我们不会多次打印每个单词。

为什么不必要的打印？

图像中的算法是：

如果 TMM识别一种语言A，我们可以为A. 假设s1, s2, s3, ... 是Σ*.

E=“忽略输入

i1) 对= 1, 2, 3, ...重复以下操作

2)在每个输入, , , 上M运行步骤。. . .is1s2s3si

3）如果任何计算接受，打印出相应sj的。”</p>

如果M接受一个特定的字符串，它将出现在生成的列表中E（实际上是无限多次）

谢谢

是否认为，如果我可以P n为每个具体的命题决定一个命题n，那么我也可以决定是否forall n, P n？感觉应该可以通过一些归纳来实现n，但是我如何在 Coq 中证明这一点？

我有以下问题：

设 n 为自然数，n > 10^100。n 能被 23 整除吗？

这个问题是半可判定的还是可判定的？

可以创建一个算法来找到答案，使其始终停止。我对半可判定和可判定之间的区别感到非常困惑。据我了解，如果我可以构建一个图灵机（算法）来接受问题的解决方案并以其他方式拒绝，那么问题是可以确定的。但是，如果机器在输入不是解决方案的情况下永远不会停止，则意味着问题是半可判定的。

所以，我想说上面的问题是可以判定的，但我不知道我说的是否正确。你能帮我找出答案吗？为什么？谢谢你。

{⟨M,N⟩ | L(M)∩L(N) 中的所有字符串都以 110 开头。}

我认为这种语言是可判定的。我们可以制作一个图灵机 TM，它以 为输入。对于 L(M)∩L(N) 中的每个字符串，如果字符串以 110 开头，在前 3 位之后，我们停止并接受。如果前三位不是 110，我们就停止并拒绝。如果字符串不在 L(M)∩L(N) 中，我不确定我们该怎么做。

总的来说，我不确定我的图灵机是否真的在工作。我能得到一些反馈吗？

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

我在一本书（Hromkovic，通信复杂性和并行计算）中读到，有无限数量的非递归 - 可枚举（非 RE）语言仅由一个元素组成？但这可能吗？我认为对于非 RE（甚至不可判定）的语言，语言必须是无限的。

我需要设计一个有效的决策过程来确定非确定性有限状态机接受的语言是否为空。

如果没有从初始状态到最终状态的路径，我知道机器不接受字符串。

但我正在努力证明这一点或设计程序。

谢谢

字母 Σ 上的语言 L 主要是素数当且仅当对于每个长度 l，如果 l 是素数，大多数长度为 l 的字符串确实属于 L，但如果 l 是合数，则不属于 L。令 PriPriTM = {〈M〉 : L(M) 主要是素数并且 M 是一个 TM}。

PriPriTM Turing 是可判定的吗？

我被要求证明以下集合是可判定的、半可判定的还是非半可判定的：

换句话说，它是一组输入，使得存在一个用自然 y 和输入 p 编码的图灵机返回其输入。

将集合 K 视为自然集合，使得用 x 和输入 x 编码的图灵机停止。这被证明是一个不可判定的集合。

我认为我需要的是找到 K 到 L 的约简，但我不知道如何证明 L 是可判定的、半可判定的或不可半可判定的。

我有一台图灵机 M，我已经证明 M 不是决策者。然后我证明了 A=L(M) 或 M 识别的语言 A。我现在被问到“语言（A）图灵可判定”。

我的问题是，如果我已经证明 M 不是决策者，我能不能用它来暗示语言 (A) 不是图灵可判定的？在我看来，机器 M 的语言不仅包括公认的语言，还包括永不停止的无限长字符串。那会使语言也不是图灵可判定的吗？

感谢您的任何建议。