Semi-Decidable Decision Problem

computation

Definition

Semi-Decidable Decision Problem

A decision problem $\mathcal{P}$ is called semi-decidable if there exists a program $\Pi$ with the following properties:

• $\Pi$ takes every instance $I$ of $\mathcal{P}$ as input.
• If $I$ is a yes instance then $\Pi$ outputs true.
• If $I$ is a no instance then $\Pi$ can either outputs false or never halts.

Paraphrased: $\Pi$ runs properly on all positive instances of $\mathcal{P}$, but we allow it to run endlessly for all negative instances of $\mathcal{P}$.