Decidable Decision Problem

computation

Definition

Decidable Decision Problem

Let $\mathcal{P}=⟨D,Y⟩$ be a decision problem and $L[\mathcal{P},\mathrm{enc}]$ its language over a finite alphabet $\Sigma$.

Then, $\mathcal{P}$ is called decidable if there is a Turing Machine that halts on every $w\in {\Sigma }^{\ast }$ (set of all strings) and accepts exactly those $w\in L[\mathcal{P},\mathrm{enc}]$.

Semi-Decidability

Given that semi-decidability is a weaker form of decidability, every decidable decision problem is semi-decidable.