布魯姆公理(Blum axioms)用以刻畫計算複雜性測度的兩條公理.它是由布魯姆(Blum , M.)於1967年引進的.設{}P,.};E。為全體一元部分遞歸函式的能行枚舉.}_ {};),E},為部分遞歸函式的一個序列.
基本介紹
- 中文名：布魯姆公理
- 外文名：Blum axioms
布魯姆公理(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”之遞歸性來替代.
