A decision problem is a family of yes/no questions p together with a “decision mapping” d: p _ {yes,no}.
Membership problem for Turing machines: given a Turing machine T, and an input w__* for T, is w_L(T)?
The membership problem is a “2 parameter” decisionsince to identify an instance of the problem, there aretwo independent arguments to be supplied.
Previous slide | Next slide | Back to first slide | View graphic version |