Definition
Semi-Decidable Decision Problem
A decision problem
is called semi-decidable if there exists a program with the following properties:
takes every instance of as input. - If
is a yes instance then outputs true. - If
is a no instance then can either outputs false or never halts. Paraphrased:
runs properly on all positive instances of , but we allow it to run endlessly for all negative instances of .