更改

跳到导航 跳到搜索
无编辑摘要
第501行: 第501行:  
! 编号 !! 比较条目 !! 图灵停机问题 !! 哥德尔定理
 
! 编号 !! 比较条目 !! 图灵停机问题 !! 哥德尔定理
 
|-
 
|-
| 1 !! 基本符号 || 程序设计语言的基本符号,诸如“if then, for, loop...” || 谓词逻辑符号:“~,∧,∨,∃,∀”,算 数运算符:“+,×,=”,数字,变量等等
+
| 1 || 基本符号 || 程序设计语言的基本符号,诸如“if then, for, loop...” || 谓词逻辑符号:“~,∧,∨,∃,∀”,算 数运算符:“+,×,=”,数字,变量等等
 
|-
 
|-
| 2 !! 基本单元 || 基本符号拼接出的完整的计算机程序,例如“Print("hello world");” || 基本符号拼接出的合法的命题语句,诸 如:“∀a: ~(a+1)=0”
+
| 2 || 基本单元 || 基本符号拼接出的完整的计算机程序,例如“Print("hello world");” || 基本符号拼接出的合法的命题语句,诸 如:“∀a: ~(a+1)=0”
 
|-
 
|-
| 3 !! 计算 || 计算机程序对字符串操作产生新的字符串 || 命题语句根据公理和规则推导产生新的命题语句
+
| 3 || 计算 || 计算机程序对字符串操作产生新的字符串 || 命题语句根据公理和规则推导产生新的命题语句
 
|-
 
|-
| 4 !! 单元编码 || 程序的源代码(字符串) || 命题的哥德尔编号
+
| 4 || 单元编码 || 程序的源代码(字符串) || 命题的哥德尔编号
 
|-
 
|-
| 5 !! 层次混淆 || 程序P去读另一个程序S的源代码s,并进行运算P(s) || 将一个命题的哥德尔编号n输入给包含自由变元的命题,并完成运算f(n)
+
| 5 || 层次混淆 || 程序P去读另一个程序S的源代码s,并进行运算P(s) || 将一个命题的哥德尔编号n输入给包含自由变元的命题,并完成运算f(n)
 
|-
 
|-
| 6 !! 单元意义 || 程序是否停机(停或不停) || 命题是否正确(真或假)
+
| 6 || 单元意义 || 程序是否停机(停或不停) || 命题是否正确(真或假)
 
|-
 
|-
| 7 !! 有意义的单元集合 || 所有的停机的计算机程序,数据对:(x,y)。即当x作用到y上面的时候X(y)停机 || 所有的定理,即根据公理和推理规则推 单元集合 导出的命题语句。我们希望所有的定理 都是真的(一致性),并且所有的真命题
+
| 7 || 有意义的单元集合 || 所有的停机的计算机程序,数据对:(x,y)。即当x作用到y上面的时候X(y)停机 || 所有的定理,即根据公理和推理规则推 单元集合 导出的命题语句。我们希望所有的定理 都是真的(一致性),并且所有的真命题
 
都是定理(完备性)
 
都是定理(完备性)
 
|-
 
|-
| 8 !! 系统自身给出的意义判断 || H(x,y)函数:判断源代码为x的计算机程序作用到数据y上面是否停机 || 语句“∃m:T(m,n)”,即“存在一个自然数m,使得m和n构成证明对”,也就是“n所代表的命题是一个定理”
+
| 8 || 系统自身给出的意义判断 || H(x,y)函数:判断源代码为x的计算机程序作用到数据y上面是否停机 || 语句“∃m:T(m,n)”,即“存在一个自然数m,使得m和n构成证明对”,也就是“n所代表的命题是一个定理”
 
|-
 
|-
| 9 !! 蒯恩函数 || 计算机程序Q(x),定义为:让程序X读入自己的源代码,即Q(x)="X(x)" || 函数Q(n),定义为:将一个包含自由变元的语句N的编号n代入其自身的自由变元中,即 Q(n)=N(n)
+
| 9 || 蒯恩函数 || 计算机程序Q(x),定义为:让程序X读入自己的源代码,即Q(x)="X(x)" || 函数Q(n),定义为:将一个包含自由变元的语句N的编号n代入其自身的自由变元中,即 Q(n)=N(n)
 
|-
 
|-
| 10 !! “我” || Q(q),就是将蒯恩函数Q的源代码q(字符串)喂给函数Q它自己的代码。Q(q)为一个字符串,Q(q)="Q(q)" || Q(q),将函数Q自己的哥德尔编号q喂给函数Q。Q(q)得到的数就是它自己的哥德尔配数。Q(q)=c(Q(q))。
+
| 10 || “我” || Q(q),就是将蒯恩函数Q的源代码q(字符串)喂给函数Q它自己的代码。Q(q)为一个字符串,Q(q)="Q(q)" || Q(q),将函数Q自己的哥德尔编号q喂给函数Q。Q(q)得到的数就是它自己的哥德尔配数。Q(q)=c(Q(q))。
 
|-
 
|-
| 11 !! 悖论函数 || 程序D(z),他是蒯恩程序与判断程序H(x,y)的结合,即D(z)=H(z,z)=H(Q(z)),其中z为输入的参数 || 函数Q<u>о</u>T,也就是蒯恩函数Q(x)与意义判断语句的结合: Q<u>о</u>T(n)=“~∃m: T(m,Q(n))”,其中 n 为一个自由变元
+
| 11 || 悖论函数 || 程序D(z),他是蒯恩程序与判断程序H(x,y)的结合,即D(z)=H(z,z)=H(Q(z)),其中z为输入的参数 || 函数Q<u>о</u>T,也就是蒯恩函数Q(x)与意义判断语句的结合: Q<u>о</u>T(n)=“~∃m: T(m,Q(n))”,其中 n 为一个自由变元
 
|-
 
|-
| 12 !! 悖论单元 || 当程序D作用到它自己的源代码上,即D(d),表示“我不停机”。 || G,当函数Q<u>о</u>T作用到它自己的哥德尔编码q<u>о</u>t上所产生的哥德尔语句即G=“~∃m:T(m,Q(q<u>о</u>t))”,表示“我不是定理”。注意,Q(q<u>о</u>t)得到的就是G的编码
+
| 12 || 悖论单元 || 当程序D作用到它自己的源代码上,即D(d),表示“我不停机”。 || G,当函数Q<u>о</u>T作用到它自己的哥德尔编码q<u>о</u>t上所产生的哥德尔语句即G=“~∃m:T(m,Q(q<u>о</u>t))”,表示“我不是定理”。注意,Q(q<u>о</u>t)得到的就是G的编码
 
|-
 
|-
| 13 !! 二律背反 || 当H(d,d)判断D(d)停机的时候,D(d)自己的表现为不停机;而当H(d,d)判断不停机的时候,D(d)又会停机 || 当G是一个定理的时候,根据G自己的意思,G不是一个定理(破坏了一致性);当G不是一个定理的时候,我们知道G是一个真句子(破坏了完备性)
+
| 13 || 二律背反 || 当H(d,d)判断D(d)停机的时候,D(d)自己的表现为不停机;而当H(d,d)判断不停机的时候,D(d)又会停机 || 当G是一个定理的时候,根据G自己的意思,G不是一个定理(破坏了一致性);当G不是一个定理的时候,我们知道G是一个真句子(破坏了完备性)
 
|-
 
|-
| 14 !! 结论 || 判断一切函数X作用到数据y上是否停机的计算机程序H(x,y)不存在 || 公理系统的一致性和完备性不能同时被满足
+
| 14 || 结论 || 判断一切函数X作用到数据y上是否停机的计算机程序H(x,y)不存在 || 公理系统的一致性和完备性不能同时被满足
 
|}
 
|}
  

导航菜单