3,094
个编辑
更改
跳到导航
跳到搜索
第468行：
第468行： − 3. '''套 SRT'''：存在编号 f，使 <math>\phi_f(x) = \psi(f, x)</math>。SRT 在这一步把参数 <math>z</math> 换成了 <math>f</math> 自己，循环闭合：<math>\phi_f(x) = \text{若} H(f, f) = 1，\text{则发散；若 }H(f, f) = 0\text{，则输出 0。}</math>+ − 4. '''代入 <math>x = f</math> 制造矛盾'''：若 <math>H(f,f)=1</math>（<math>H</math> 说"<math>f</math> 在输入 <math>f</math> 停机"），但此时 <math>\phi_f(f)</math> 发散——<math>H</math> 判错；若 <math>H(f,f)=0</math>（<math>H</math> 说不停机），但此时 <math>\phi_f(f)=0</math> 停机——<math>H</math> 又判错。于是 <math>H</math> 无论如何都错 <math>\to </math>'''<math>H</math> 不存在'''。∎+
→图灵停机问题（1936）
# '''假设'''存在判定器 <math>H</math>（<math>H(e,x)=1</math> 表示"程序 <math>e</math> 在输入 <math>x</math> 停机"，<math>=0</math> 表示不停机）。
# '''假设'''存在判定器 <math>H</math>（<math>H(e,x)=1</math> 表示"程序 <math>e</math> 在输入 <math>x</math> 停机"，<math>=0</math> 表示不停机）。
# '''写出"想要的行为"，把"自己"写成参数 <math>z</math>'''：我们要一个与 <math>H</math> 唱反调的捣乱程序——"如果 <math>H</math> 说程序 <math>z</math>（在输入 <math>z</math> 上）会停机，我就死循环；如果 <math>H</math> 说不停机，我就立即停机"。写成可计算规则：<math>\psi(z, x) = \text{若} H(z, z) = 1，\text{则发散（死循环）；若} H(z, z) = 0，\text{则输出0（立即停机）。}</math>
# '''写出"想要的行为"，把"自己"写成参数 <math>z</math>'''：我们要一个与 <math>H</math> 唱反调的捣乱程序——"如果 <math>H</math> 说程序 <math>z</math>（在输入 <math>z</math> 上）会停机，我就死循环；如果 <math>H</math> 说不停机，我就立即停机"。写成可计算规则：<math>\psi(z, x) = \text{若} H(z, z) = 1，\text{则发散（死循环）；若} H(z, z) = 0，\text{则输出0（立即停机）。}</math>
# '''套 SRT'''：存在编号 f，使 <math>\phi_f(x) = \psi(f, x)</math>。SRT 在这一步把参数 <math>z</math> 换成了 <math>f</math> 自己，循环闭合：<math>\phi_f(x) = \text{若} H(f, f) = 1，\text{则发散；若 }H(f, f) = 0\text{，则输出 0。}</math>
# '''代入 <math>x = f</math> 制造矛盾'''：若 <math>H(f,f)=1</math>（<math>H</math> 说"<math>f</math> 在输入 <math>f</math> 停机"），但此时 <math>\phi_f(f)</math> 发散——<math>H</math> 判错；若 <math>H(f,f)=0</math>（<math>H</math> 说不停机），但此时 <math>\phi_f(f)=0</math> 停机——<math>H</math> 又判错。于是 <math>H</math> 无论如何都错 <math>\to </math>'''<math>H</math> 不存在'''。∎
关键就在第 3 步：<math>\psi</math> 里用的是参数 <math>z</math>（可以正常定义），SRT 把它换成 <math>f</math> 自己——'''没有 SRT，"<math>\phi_f</math> 的行为取决于 <math>H</math> 对 <math>f</math> 的判决"就是非法循环定义，写不出来'''。SRT 的全部威力，就是把这种循环合法化：你只管把"自己"写成参数，存在性交给定理<ref name="moschovakis2010" /><ref name="rogers1967" />。
关键就在第 3 步：<math>\psi</math> 里用的是参数 <math>z</math>（可以正常定义），SRT 把它换成 <math>f</math> 自己——'''没有 SRT，"<math>\phi_f</math> 的行为取决于 <math>H</math> 对 <math>f</math> 的判决"就是非法循环定义，写不出来'''。SRT 的全部威力，就是把这种循环合法化：你只管把"自己"写成参数，存在性交给定理<ref name="moschovakis2010" /><ref name="rogers1967" />。