ブラムの公理
例えば状態記号の数が q {\displaystyle q} でテープ記号の数 s {\displaystyle s} のチューリング機械を考えると、テープ状態の総数は s t {\displaystyle s^{t}} でありヘッド位置の総数は t {\displaystyle t} であるから、系全体の取りうる状態の数は高々 q s t t {\displaystyle qs^{t}t} である。したがって計算を十分な時間だけ走らせれば、計算が終了するか、ある状態が繰り返し現れて無限ループに陥るか、または空間量の制限を超過するかの何れかが起こる。その何れであるかは実効的に判定できるから、したがって Φ e ( x ) = t {\displaystyle \Phi _{e}(x)=t} であるか否かは計算可能である。
( φ , φ ) {\displaystyle (\varphi ,\varphi )} は2番目の公理を満たさないから複雑性測度ではない。