Definition
Semi-decidable Predicate
A predicate
on is semi-decidable if its partial indicator function is partially computable. Here,
is an input tuple. The procedure doesn’t have to halt on every input , returning when holds and otherwise.
Semi-decidable Predicate
A predicate
on is semi-decidable if its partial indicator function is partially computable. Here,
is an input tuple. The procedure doesn’t have to halt on every input , returning when holds and otherwise.