非整齐的自动机是否有不可确定的属性？

Question

线性界限自动机（避免使用空的语言技巧）是否存在不可确定的属性？确定性有限的自动机呢？ （放弃棘手）。

我想获得一个定义的不确定问题的示例（如果可能的话） 不使用图灵机 明确。

图的完整性是支持不可兼容问题所需的模型吗？

Answer 1

关于无上下文的语法的不可确定的问题，因此也是下降受体，这是受限制的TMS 来自维基百科...

1. 给定CFG，它是否在规则中使用的终端符号的字母上生成了所有字符串的语言？

2. 给定两个CFG，它们会生成相同的语言吗？

3. 给定两个CFG，第一个可以生成第二个可以生成的所有字符串？

关于CFGS/PDA以及CSGS/LBA以及许多其他“简单比TM”模型，还有许多其他有关CFGS/PDA的信息。

Answer 2

目前尚不清楚您在问题的后面部分要求什么，主要是因为未定义“有关机器模型的问题”。

我想获得一个不可确定的问题的示例，而无需图灵机器

令$ {m_i } $为一类机器，让我们使用$ i $作为$ m_i $的代码。我们可以将$ i $也解释为$ i $ th tm的代码，然后问给定$ m_i $ $ i $ th tm停止吗？大约$ m_i $ s的问题是不可决定的。

语言只是一组字符串，您分配给字符串的解释对语言的可决定性没有影响。除非您正式定义您的含义 机器型号 和 这些机器的问题 您以后的问题无法回答。

图灵（Turing）是否完成了最小的机械来支持不可确定的问题？

同样，我上面提到的观点适用。一个更合理的问题是：所有不可证明的证明是否经历了类似于TMS停止问题的不可证明的事情？ （答案是：还有其他方法）。

另一个可能的问题是：TMS最小的子集是什么，其中停止问题是无法确定的。显然，这样的一类应包含不停止的问题（否则问题是可行的）。我们可以轻松地创建TMS的人工子集，在如果不能够计算任何有用的内容的情况下，停止问题是无法决定的。一个更有趣的问题是关于大型TMS的大型TMS，其中停止对他们来说是可决定的。

这是另一点：一旦您具有很小的操纵位的能力（例如多项式尺寸$ mathsf {cnf} $），您就可以创建一个带有三个输入的机器$ n $：$ e $，$ x $，并且$ c $使其输出1 iff $ c $是一个停止，接受输入$ x $的TM $ M_E $的计算。然后，您可以问以下问题：$ c $ st $ n（e，x，c）$是1吗？这是一个不确定的问题。

Answer 3

对于有限状态自动机来说，存在一个非常简单的不确定问题。将字母分成两个半$ sigma cup bar sigma $，其中$ bar sigma $中的字母被“禁止”副本。现在，给定有限的状态自动机$ a $ a $ a $ over $ sigma cup bar sigma $决定它是否接受字符串，使得未挂载的零件等于禁止的零件（如果我们忽略了棒）。例如，字符串$ aa bar a bar ab bar b bar aa $都可以（两个零件拼写$ aaba $）。

是的，这是隐藏在有限状态自动机中的后通信问题。在问题中，图灵完整性远非显而易见。在背景中，它在那里，正如两份副本（未挂牌和禁止）一起编码一个队列，这本身就是图灵的力量。

Answer 4

“是否可以为比图灵机功能强大的自动机构建立一个不确定的问题吗？”'

是的。自动机是数字理论的一致公理公式（例如，请参见 (1)），因此 戈德尔的第一次不完整定理 它必须包括不确定的命题。

例子：

任何问题 对于TM，对于TM可以模拟的任何自动机来说，这是不可决定的。为什么？因为如果一个不如TM强大的自动机可以决定TM无法决定的语言，则TM应该能够通过以矛盾的矛盾模拟自动机来决定它。

Answer 5

Emil Post希望找到这个问题的答案：是否存在不解决停止问题的非恢复性（不可竞争）集。他只有部分成功，但他所做的就是创造所谓的 简单集.

来自Wikipedia：

如果自然群体是悬空的并递归枚举，则称为简单的子集，但其补体的每个无限子集都无法递归地枚举。简单的集合是递归枚举集的示例，这些集合不是递归的。看看Wikipedia文章以获取更多信息和参考， 简单集.