TCS 学习笔记 [6] 不可解问题
最编程
2024-03-20 21:53:20
...
A:
\(\Pi = (N,Y_\Pi)\)
\(Y_\Pi = \{x|HALT(l(x),r(x))\}\)
注：一元谓词\(HALT(l(x),r(x))\)不可计算，则\(\Pi\)不可判定。
A: \(D_\Pi\)是待考察判定问题的参数取值范围（“论域”）
\(Y_\Pi\)是待考察判定问题应当判定为是的元素集合。
\(P_\Pi\)是\(\Pi\)诱导出的\(N\)上谓词，\(P_\Pi(x)\Leftrightarrow e^{-1}(x)\in Y_\Pi\)，其中\(e^{-1}\)是解码。我们一般认为编解码是双射。
A: \(f\)可计算，但\(f\)未必可逆。想判定\(I\in Y_{\Pi_1}\)时，可以能行计算出\(f(I)\)，然而反过来不一定可以能行计算。
所以说此时\(\Pi_2\)解决了\(\Pi_1\)也解决了，\(\Pi_1\)归约到\(\Pi_2\)
A: 如果其对应整数集\(A\) r.e.则\(A\)是某可计算函数\(g\)值域，则\(\Phi_{g(x)}(y)\)为全函数，且所有的\(g(x)\)对应了所有的全函数。
设\(f(x)=\Phi(x,g(x))+1\)则\(f\)可计算，且\(f(x)\ne \Phi_{g(x)}(x)\)，\(f\)与任意\(\Phi_{g(x)}\)都不同，矛盾。
A: 平时是未知归约到可解。现在是不可判定归约到未知。
本质是“逆否命题”，即A归约到B，A不可判定则B不可判定，B可判定则A可判定。
上一篇： 使用 vue3 的 pinia