Paper 2, Section I, F
Part II, 2020
Assuming the definition of a partial recursive function from to , what is a recursive subset of ? What is a recursively enumerable subset of ?
Show that a subset is recursive if and only if and are recursively enumerable.
Are the following subsets of recursive?
(i) codes a program and halts at some stage .
(ii) codes a program and halts within 100 steps .