unbounded search operator
let
, where
is some polynomial with integer coefficients and where
denotes "the least
such that
".
[cite:;taken from @computability_soare_1987 chapter 1 recursive functions]
[cite:;taken from @computability_soare_1987 chapter 1 recursive functions]
if
is a partial computable function, and
then
is a partial computable function.
[cite:;taken from @computability_soare_2016 theorem 1.5.3]
[cite:;taken from @computability_soare_2016 theorem 1.5.3]
let
be a PRC class, if
belongs to
, then so do the functions
and
[cite:;taken from @computability_davis_1994 theorem 6.1; chapter 3.6 iterated operations and bounded quantifiers]
the sum of functions can be used to construct the
quantifier in primitive recursive predicates, give a predicate
in some PRC class, it follows form the theorem that
is in PRC aswell because it simply can be represented by the function unbounded_search_operator.html. the same goes for the predicate
which can be represented by the function unbounded_search_operator.html.
let
belong to some given PRC class
. then by unbounded_search_operator.html the function
also belongs to
.
[cite:;taken from @computability_davis_1994 chapter 3.7 minimalization]
is called bounded minimalization.
[cite:;taken from @computability_davis_1994 chapter 3.7 minimalization]
if
belongs to some PRC class
and
, then
also belongs to
.
[cite:;taken from @computability_davis_1994 theorem 7.1]
the operation [cite:;taken from @computability_davis_1994 theorem 7.1]