Paper 2, Section I, F

Automata and Formal Languages
Part II, 2020

Assuming the definition of a partial recursive function from N\mathbb{N} to N\mathbb{N}, what is a recursive subset of N\mathbb{N} ? What is a recursively enumerable subset of N\mathbb{N} ?

Show that a subset ENE \subseteq \mathbb{N} is recursive if and only if EE and N\E\mathbb{N} \backslash E are recursively enumerable.

Are the following subsets of N\mathbb{N} recursive?

(i) K:={nn\mathbb{K}:=\left\{n \mid n\right. codes a program and fn,1(n)f_{n, 1}(n) halts at some stage }\}.

(ii) K100:={nn\mathbb{K}_{100}:=\left\{n \mid n\right. codes a program and fn,1(n)f_{n, 1}(n) halts within 100 steps }\}.