现在我们已经知道了 问题是不可判定的了,那么我们应该如何使用类似 这样的我们已经知道是不可判定了的问题呢?答案是:我们通过他们来证明更多问题的不可判定性。在这个过程中我们要使用一种叫做归约 (Reduce) 的方法。
规约简单的说,就是一个偷懒的过程,一个化简问题的过程。例如你已经知道了如何计算一个圆的面积,那如何来计算两个圆的面积呢?答案是将「计算两个圆的面积」这个我们未知的、高难度的问题化简到「做两次计算一个圆的面积」这样的我们已知的、简单的问题。这个过程就叫做归约。生活中人们经常使用归约来解决问题,当人们要去做一些有挑战性的任务时,往往第一步是思考能不能把这个问题转换成一个已经解决了的问题,这就是在无意中使用了归约的思想。
我们回归主题上来,现在我们想证明 的不可判定性。 的一般数学形式为:给定一个语言 满足: 。即给定一个图灵机的编码和一段字符串,判定这段字符串是否可以被图灵机接受。
当我们使用归约的思想来用一个已知的不可判定问题 判定另一个问题 的不可判定性时,一般步骤如下:
- 假设 可已被判定,即存在一个算法 来解决 问题。
- 设法使用 解决 问题。
- 因为 已知不可判定,即没有算法可以解决它,所以 不存在,所以 不可判定。
所以我们首先假设 问题可判定,即存在一个判别器 可以判断 。若 存在,则我们可以按如下的步骤来判断 问题:
- 对于 ,我们有一个 。首先我们检测 是否是一个图灵机。检测字符串是否为图灵机是可以被做到的,因为图灵机的编码化遵守一系列的规则,我们只需要一个规则一个规则地去检测是否合理。
- 若 不是一个图灵机,则我们可以理解为由 构成的不存在的图灵机的语言 。即 不在 所构成的不存在的图灵机的语言中。那么我们根据 的定义,接受 并停机。
- 若 是一个图灵机,那么我们把 传给 的判别器 。因为我们假定 存在,所以不管 构成的图灵机接不接受字符串 ,都会停机。
- 若判别器 告诉我们 ,则根据 定义,。若 ,则 。
于是,我们成功用 的判别器 判断了 ,但我们知道 是不可判定的,所以只有可能我们整个证明的前提发生了错误。即 不可判定。
本文作者 Auther:Soptq
本文链接 Link: https://soptq.me/2020/06/21/Lu-deciability/
版权声明 Copyright: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处。 Content on this site is licensed under the CC BY-NC-SA 4.0 license agreement unless otherwise noted. Attribution required.
发现存在错别字或者事实错误?请麻烦您点击 这里 汇报。谢谢您!