ブラムの公理
ブラム複雑性測度は特定の計算模型によらず定義されている。もっと分かりやすくする為に、ブラムの公理をチューリング機械の言葉で次のように言い換えることもできる。
ブラム複雑性測度とは、順序対 (チューリング機械 M {\displaystyle M} , 入力 x {\displaystyle x} ) から自然数または ∞ {\displaystyle \infty } への写像であって、次の公理を満たすものをいう:
Φ ( M , x ) {\displaystyle \Phi (M,x)} が無限大でないとき、かつそのときに限り M ( x ) {\displaystyle M(x)} は停止する
入力 ( M , x , n ) {\displaystyle (M,x,n)} が Φ ( M , x ) = n {\displaystyle \Phi (M,x)=n} を満たすかどうか決定するアルゴリズムが存在する
例えば、 Φ ( M , x ) {\displaystyle \Phi (M,x)} を M に x を入力して実行してから停止するまでに要するステップ数とする。1番目の公理は明らか。2番目の公理は、万能チューリング機械に M と x を入力して n ステップ目までの計算を模倣すれば判定できるからよい。