如果我可以从lh映射到l映射，它是否正确是正确的

Question

我似乎没有正确地理解语言的手段是什么。

例如，让我们说有一种名为LM的语言。

我想看看lm是否是递归的，要说，让我们发现我发现从l-halting问题减少到lm。

我假设LM是递归，所以我表明，然后L-HALTING问题也是递归，当然是假的，因此LM不是递归。

但我可以说lm是因为我找到了减少lh到lm的方法吗？ 如果不是我如何显示LM是重新的？

Answer 1

让我们清除一点，因为有许多可能导致误解的等效/类似的定义。

• 您可以显示语言 $ l $ 是通过构造递归函数 $ \ chi_l $ （或图定机器或任何其他等效计算模型），决定它，即 $$ \ chi_l（x）=begin {is} 1＆\ quad; x \在l \\ 0＆\ quad; \ text {otw}。 \结束{案例} $$ 请注意，必须为所有输入定义 $ \ chi_l $ 。

• 您可以显示一个语言 $ l $ 不是递归，通过查找来自非的“减少” - 持有人的语言。这可能是你减少的意思，它定义如下：

  我们说语言 $ a $ 是语言 $ b $ ，写入 $ a \ le_t b $ ，如果我们可以构建递归函数（或图定机器），可以决定 $ a $ < / span>假设 $ b $ 。

  如您所见，从 $ b $ to $ a $ 。

  对于任何 $ a $ 和 $ b $ 这样 $ a \ leq_t b $ ，如果 $ b $ 是递归，那么 $ a $ 。

  因此如果我们已经知道一些 $ a $ 不是递归，那么发现一个缩减 $ a \ leq_t b $ 对于任何 $ b $ 也使其不递归。

• 您可以显示语言 $ l $ 是 Re，by ConstructionG递归函数 $ \ varphi_l $ （或图定机器） $ dom（\ varphi_l）= l $ （或停止/接受它），例如 $$ \ varphi_l（x）=begin {is} 1＆\ quad; x \在l \\ \ Uprarrow＆\四边形; \ text {otw。} \结束{案例} $$

  其中 $ \ Uprarrow $ 表示“未定义”（或“不停止”）。 Re-ness还有其他定义，就像它的名称“枚举”，你可以轻松观察到相当于这个。

• 但是在显示语言 $ l $ not Re，减少没有帮助，因为它不一定转移重新。例如，观察到 $ \ overline {l_ {halt}} \ leq_t l_ {halt} $ （确实是任何语言都是图灵的补充，反之亦然），但我们知道<跨越类=“math-container”> $ l_ {halt} $ 是re，而 $ \ overline {l_ {halt}} $ 不是。

  但还有其他类型的更强的减少转移重新启动。一个这样的减少称为“多次可释放性”：

  我们说语言 $ a $ 对语言 $ b $ ，写入 $ a \ leq_m b $ ，如果有总递归函数 $ f $ 这样对于任何输入 $ x $ $$ x \在a \ iff f（x）\中，b $$

  这是一个更强的减少了 $ a \ leq_m b $ 表示 $ a \ leq_t b $ （不一定反之亦然）。所以，就像减少一样，它会转移递归。我们也有

  对于任何 $ a $ 和 $ b $ 这样 $ a \ leq_m b $ ，如果 $ b $ 是重新的，那么它是 $ a $ 。

  要查看如何实现如何，只需拍摄 $ \ varphi_a（x）=varphi_b（f（x））$ 。
  因此，显示语言 $ b $ 的正确方法是不是重新，是找到许多减少 $ a \ leq_m b $ 对于某些非重新编程 $ a $ 。请注意，上面的示例在此处不起作用，因为 $ \ overline {l_ {halt}} \ nleq_m l_ {halt} $ 。

进一步读取，请参阅

l=“nofollow noreferrer”> 计算性理论通过 s。Barry Cooper PT。我，ch。7.