enumeration theorem
there is a partial computable function of two variables
such that
. by turing's theorem there is some
such that
.
[cite:;taken from @computability_soare_2016 theorem 1.5.3]
[cite:;taken from @computability_soare_2016 theorem 1.5.3]
we write
basically
is a set of inputs that the computable function
(which has the godel number
) converges on, and it denotes the
th recursively enumerable set.
[cite:;taken from @computability_davis_1994 chapter 4 recursively enumerable set; theorem 4.6 enumeration theorem]
[cite:;taken from @computability_davis_1994 chapter 4 recursively enumerable set; theorem 4.6 enumeration theorem]
in [cite:@computability_soare_2016], the notation
is used to denote the inputs for which the function whose number is
halts on in less than
steps.
[cite:;refer to @computability_soare_2016 definition 1.6.17]
[cite:;refer to @computability_soare_2016 definition 1.6.17]
a set
is r.e. if and only if there is an
for which
.
[cite:;taken from @computability_davis_1994 theorem 4.6]
[cite:;taken from @computability_davis_1994 theorem 4.6]