table of contents

enumeration theorem

2024-03-20

there is a partial computable function of two variables such that . by turing's theorem there is some such that .

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.

in (robert i. soare, 2016), the notation is used to denote the inputs for which the function whose number is halts on in less than steps.

a set is r.e. if and only if there is an for which .