问题标签 [decidable]

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

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

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

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

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

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

I'm working on a related decidability/recognizable problem, and to solve it, I need clarification about the encoding/representation of a turing machine.

I know a turing machine is formally defined as a 7-tuple. If I have a Turing Machine U and another Turing Machine M, is it trivial to design U to recognize some part of M (such as M's alphabet, input symbols, set of accepting states, etc)?

Part of me thinks that because these are finite sets, it's trivial to count over them, but part of me wonders whether or not you can just enumerate some part of M's definition without the possibility of looping into infinity.

Arthur Dent 使用地球上尚不可用的太空时代技术开发了一种算法，该算法可确定 TM M1 在空白磁带上启动时是否停止。但后来，他发现生命、宇宙和一切的意义是42。

(a) [5] 给定一个 TM M2，证明 Arthur 可以使用他已经开发的程序确定 M2 在输入 42 上是否停止，该程序确定 TM M1 在空白磁带上启动时是否停止。如果您在证明中创建了一个新 TM，请给出其机器模式。

(b) [5] 假设有一个程序比 Arthur 的程序快，但它回答了 TM M2 是否在输入 42 上停止的问题。解释 Arthur 如何使用该算法来确定某个 TM M1 在空白处启动时是否停止胶带。如果您在证明中创建了一个新 TM，请给出其机器模式。

(c) [5] 我们在课堂上证明了确定 TM M 在空白磁带上启动时是否停止的问题是不可判定的。是 (a) 部分还是 (b) 部分可以用来证明确定 TM M 是否在输入 42 上停止也是不可判定的？

任何人都可以帮我破译我的教授在这里所说的内容吗？

如果我有一个上下文无关语法 G 使得 G 的语言为零，那么 G 是可判定的吗？

我知道答案是肯定的，但我无法证明这一点。我的第一个想法是说只有一个状态 q1，它是相当于 G 的图灵机的启动状态和接受状态。这台机器将不接受任何输入并立即停止并接受，因为它已达到接受状态状态。这是一个可以接受的答案，还是我离开这里？

编辑：

正如乔尔在下面所说，我描述的语言接受所有字符串。为了解决这个问题，我建议使用第二台机器 G'。G' 有 3 个状态，开始状态 q1、接受状态 q2 和拒绝状态 q3。q1 在 G' 字母表中的所有符号上都转换为 q3，q2 也是如此。q1 有一个到 q2 的 epsilon 转换。因此，如果提供给 G' 的字符串中存在任何符号，则 G' 将拒绝。如果没有符号，唯一的选择是将 epsilon 转换为接受状态。听起来怎么样？

编辑：

上面的解决方案被证明可以接受语言 L(G') = {""}。

我正在为这是否可以确定而苦苦挣扎：

A = {x 是自然数集的一个元素 | 对于每个大于 x 的 y，2y 是两个素数之和}

我倾向于认为这是可以决定的，因为当输入图灵机时，它永远不会达到接受状态并无限循环，除非它拒绝。但是，我也知道，要确定一种语言，必须只存在一种算法来确定它；我们不一定要知道它是如何完成的。有了这个，我的一部分认为它是可判定的？有人知道如何证明吗？

我想创建一个 Num 的超类，称为 Linear

我得到错误：

据我了解，该行的某些内容instance (Num a) => Linear a where不正确。（如果我使用标志，它会编译-XFlexibleInstances -XUndecidableInstances：）

有没有办法在不使用那些可怕的标志的情况下实现这一目标？（而上面的代码到底有什么无法确定的？？）

更新：向线性添加多项式类型。

添加多项式后，它甚至不会使用这些标志进行编译并给出错误：

我对不可判定问题和 NP 难题之间的关系有点困惑。NP难问题是不可判定问题的子集，还是它们只是相同且相等，还是它们不可比较？

对我来说，我一直在和我的朋友争论，不可判定的问题是 NP 难题的超集。会存在一些在 NP 中不难但无法确定的问题。但是我发现这个论点很弱并且有点困惑。是否存在不可判定的 NP 完全问题。NP难有什么问题是可判定的吗？？

一些讨论会有很大帮助！谢谢！

L = {<T> | T 是识别 {00, 01}} 的图灵机

证明 L 是不可判定的。

我真的很难理解这里使用的减少。

我不是要免费午餐，只是朝着正确的方向前进。

我写了一些需要 -XUndecidableInstances 来编译的 Haskell 代码。我确实理解为什么会发生这种情况，因为违反了某个条件，因此 GHC 大喊大叫。

但是，我从未遇到过类型检查器实际上会挂起或陷入无限循环的情况。

非终止实例定义是什么样的 - 你能举个例子吗？