布鲁姆公理(Blum axioms)用以刻画计算复杂性测度的两条公理.它是由布鲁姆(Blum , M.)于1967年引进的.设{}P,.};E。为全体一元部分递归函数的能行枚举.}_ {};),E},为部分递归函数的一个序列.

布鲁姆公理(Blum axioms)用以刻画计算复杂性测度的两条公理.它是由布鲁姆(Blum , M.)于1967年引进的.设{}P,.};E。为全体一元部分递归函数的能行枚举.}_ {};),E},为部分递归函数的一个序列.下列两条便称为布鲁姆公理:

B1.对任何i , dom恤)=dom)，

B2.如果以M(i ,x, y)表示谓词};(x)=y，则M(i,x,y)为一个递归谓词(即可判定的).

满足布鲁姆公理的中，称为布鲁姆测度或复杂性测度.由于中，是用以表示对应于毋的算法的计算复杂性，因此，中称为(犯的)计步函数.这样，中当然应与尹具有相同的定义域(即Bl ).而公理B2则保证了可以能行地确定一个特定的计算能否在某个能行的界内收敛.而且，B2中关于“};(x)=y”的递归性条件也可以等价地用“}; (x)Gy”或“};(x)Gy”之递归性来替代.