网站首页  情感咨询  情感美文  情感百科  情感生活  学习充电  旧版美文

请输入您要查询的百科知识:

 

标题 判定问题
类别 哲学
释义 判定问题     decision problem

如何寻找一种方法,去判定某一个事物是否具有某种属性的问题。主要指公式的可证性、普遍有效性和可满足性。在数理逻辑中,一个判定问题有如下的一般形式:给出一个集合A和一性质P,去寻找一个算法,使它能告知对于集合A中的任何元素a(即a∈A),是否具有性质P;或者能证明不可能找到这样的算法。例如:自然数n是偶数吗?这里自然数n组成的集合N,就相当于一般形式中的集合A,“是偶数吗”?相当于性质P。它构成一个判定问题:可以用符号写成:

{自然数n是偶数吗?|n∈N}

显然这个判定问题存在一个算法,对于N中的任一个自然n,则只需用2去除。如果余数为0,那么n就是偶数;如果余数为1,n就不是自然数。这一算法适用于一切自然数。给出一个数论谓词(或一个数论关系),或依赖于若干参数的问题类M(x1,…,xn),对任意数a1,…,an∈N,问M(a1,…,an)是否成立或是否真的判定问题又往往可归结为给定N的一个子集A,对任意x∈N,问x是否属于A?如能找到一个机械的方法(或算法),用它可对任意a1,…,an∈N,能在有限步内判定M(a1,…,an)是否成立,或对任意x∈N,能在有限步内判定x是否在A中,则称相应的判定问题是能行可解的。如找不到所要的算法,则称相应的判定问题是能行不可解的。如果使用了丘奇论点,那末判定问题则成为是否能找到某个递归函数的问题,或成为证明某个数论函数是否可计算的问题。令:

或:

若CM(或CA)是一个递归函数(或是可计算的),则称相应的判定问题M(x1,…,xn)(或x∈A?)是递归可解的,或递归可判定的。若CM(或CA)不是一个递归函数(或不可计算),则称相应的判定问题是递归不可解的,或递归不可判定的。

再令:

或:

若CM(或CA)是一个递归部分函数(或是可计算的),则称相应的判定问题是半可解的,或是半可判定的。

随便看

 

依恋情感网情感百科知识大全收录了49620条情感类百科知识词条,覆盖心理学、哲学、美学等领域,基本涵盖了日常生活中常见问题的详细解释,是情感生活的有利工具。

 

Copyright © 2002-2024 yiyi18.com All Rights Reserved
更新时间:2025/8/4 5:42:08