ライスの定理
φ : N → P ( 1 ) {\displaystyle \phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}} は計算可能関数へのゲーデル数割り当てであると解釈できる。
P ( 1 ) {\displaystyle \mathbf {P} ^{(1)}} の部分集合と、計算可能関数の属性を同一視する。 すなわち集合 F ⊆ P ( 1 ) {\displaystyle F\subseteq \mathbf {P} ^{(1)}} に対し、 φ e ∈ F {\displaystyle \phi _{e}\in F} であるときだけ計算可能関数 φ e {\displaystyle \phi _{e}} が属性 F を持つと解釈する。
F ⊆ P ( 1 ) {\displaystyle F\subseteq \mathbf {P} ^{(1)}} に対し、「自然数 e {\displaystyle e} が与えられたとき、 φ e ∈ F {\displaystyle \phi _{e}\in F} であるかどうかを決定せよ」という決定問題を D F {\displaystyle D_{F}} と書く。