Language of a Decision Problem

computation

Definition

Language of a Decision Problem

Fix a finite alphabet $\Sigma$ and a computable encoding $\mathrm{enc}:D\to {\Sigma }^{\ast }$. The language of a decision problem $\mathcal{P}=⟨D,Y⟩$ with an encoding $\mathrm{enc}$ is

$$L[\mathcal{P},\mathrm{enc}]=\{\mathrm{enc}(x)\mid x\in Y\}\subseteq {\Sigma }^{\ast }.$$