前缀语言的可决定性

Question

在中期，有以下问题的变体：

对于可定义的$ l $定义$$ text {pref}（l）= {x mid envists y text {st} xy in l } $ j $ $不一定是可决定的。

但是，如果我选择$ l = sigma^*$，那么我认为$ text {pref}（l）$也是$ sigma^*$，因此可以决定。 $ l = emptyset $也给出了相同的结果。而且由于$ l $必须是可决定的，所以我无法选择停止问题。

1. 我如何找到$ l $这样的$ text {pref}（l）$是不可决定的？
2. $ l $的哪些条件将使$ text {pref}（l）$ deciDable，哪些会使它无法确定？

Answer 1

请注意，在可定义的语言面前使用存在的量词，我们可以获得任何RE语言，即每个RE语言都可以表达为

$ {x in sigma^* mid in in sigma^* langle x，y rangle in V } $$

其中$ v $是一种可决定的语言。其中包括$$ a_ a_ {tm} = { langle e，x rangle mid text {$ e $编码$ x $ x $} } $$的不可决定的语言。

这里唯一的区别是，我们必须自己分开$ x $和$ y $。标准技巧是使用新符号将两个部分分开（假设分离器属于$ y $）。因此，可以以这种格式表示任何RE语言（包括不可决定的语言）。

对于第二个问题，没有一般算法的方法来检查给定可决定语言的前缀是否不可决定。这是赖斯定理的。

Answer 2

元知识：您想找到一种不可确定的语言，尽管如此，该语言仍然具有一些计算属性。任意不可用的语言可能不会引导您很远。但是一个半决赛…

---

更强的提示：什么是半独立语言？这意味着我们可以列举这些单词：这是一些单词$ u $，因此存在整数$ n $

$$ u = f（n）$$

凝视这个方程式，考虑到可决定性和前缀。

---

直观地说，假设您有一些$ x $，并且想测试它是否在$ mathrm {pref}（l）$中。通常，您不会比检查$ xa $，$ xb $，$ xaa $等要好。其中$ a，b， cdots $是字母的字母。这是一个部分递归功能，可在$ mathrm {pref}（l）$中测试成员资格。当然，我们知道$ mathrm {pref}（l）$已经是RE；我们需要显示的是，有时没有其他方法。让我们以某些$ s subset mathbb {n} $的套装来进行一些集合，而不是递归，让$ f $是$ s $的枚举（$ s = {f（x） reid x in in in mathbb { n}} $）。

假设字母包含三个符号$ 0 $，$ 1 $和$：$（如果只有两个符号$ { aleph， beth } $，encode $ 0 $ as $ aleph aleph aleph $，$ 1 $ as $ as as $ Aleph beth $和$：$ as $ beth $）。如果$ n in mathbb {n} $，让$ bar n $ be n $ be bas bas base 2使用符号$ 0 $和$ 1 $写成，而没有引导$ 0 $。

令$ l = { bar y mathord： bar x mid y = f（x）} $。用简单的英语，我们正在采用$ s $的要素，并处理其枚举指数。 $ l $显然是可以决定的（检查有一个$：$，两个数字序列没有引导$ 0 $，并且第一个数字序列将图像拼写为第二个数字的$ f $） 。然而，确定某些$ bar y $是$ l $的前缀是否涉及确定$ y $是否在$ s $中，您不能在不知道$ x $的情况下做到这一点，因为$ s $不是通过假设递归的。正式地，$ mathrm {pref}（l）$是无法决定的，因为$ mathrm {pref}（l） cap {0,1 }^* mathord：= s mathord：$ notable：$不可决定。