补充资料：不可判定性

不可判定性
IndecidalHlity

　　不可判定性【1”‘cida城勿;一epa3pe“HMocT‘1【补注】一个算法(日即riUllll)的不存在性，或者在一个形式系统(forn以1 systeTn)中证明或否证一个命题的不可能性.下面分别予以讨论.解决某一给定问题的算法的不存在性常常称为该问题的不可解性(un-solvabiljty).有时“不可判定性”和“不可解性”看作是同义词.(见不可解性(unsolvability).) 在一切数学领域中都可得到判定性结果，它们可能以算法的直观概念为依据.由构造一个算法证明一个问题是可判定的，该算法在接收该问题一个例子的数据后产生对于这个例子的回答.一个经典例子是求两个自然数的最大公因子的Euelid算法. 算法的概念必须形式化才能证明某个问题是不可判定的.一个问题的不可判定性是指算法原则上不可能存在，—不仅仅是至今还不知道这样的算法. 在这些形式化中最普通的是1物由犯机(T以角glna-chjne).然而，应该强调，所有提出的形式化发现都是等价的，此外，不可判定问题的存在性是不依赖所用的形式化.下面将简要阐述这一点. 这样，必须说明算法这个直观概念的任何形式化如何导致算法不可判定问题.考虑任何一个这样的形式化.对任何算法A和A的任何输人字x，存在两种可能性:或者A对于x停止(llah)，即当A作用于x时得出一个停止的计算;或者A对于x不停止.在后一种情况下，就说A对于x循环(loop).停机问题(回t叱problelll)是对于任何对(A，x)，判定A对于义是停止还是循环. 停机问题的一个特例是可自应用性问题(seif一app-licability problem)，定义如下.每个算法A是由它的Godel字(Gi记el word)g(A)所完全决定的.例如，抓A)可定义为A中所有指令按顺序的集合.一个算法A称为可自应用的(se】f一applicable)，只有当A对于夕(A)停止.自应用问题是判定任一算法是否可自应用的.自应用问题是停机问题的子问题;因此，如果前者是不可判定的，则后者也是不可判定的. 假设存在一个自应用问题的算法A。.这样，对所有形为g(A)的输人，A。都停机，且根据A是否可自应用产生回答yes或no.现在修改A。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。