ブラムの公理
ブラム複雑性測度(英: Blum complexity measure)とは、1変数部分計算可能関数のアクセプタブル・ナンバリング φ {\displaystyle \varphi } と、計算可能関数
Φ : N 2 → N {\displaystyle \Phi :\mathbb {N} ^{2}\to \mathbb {N} }
の組 ( φ , Φ ) {\displaystyle (\varphi ,\Phi )} で、次のブラムの公理を満たすものをいう。
φ i {\displaystyle \varphi _{i}} の定義域と Φ i {\displaystyle \Phi _{i}} の定義域は等しい
集合 { ( i , x , t ) ∈ N 3 | Φ i ( x ) = t } {\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}} は計算可能である