I prepare for local complexity contest and review some old question banks. I get stuck in one problem and no idea how we can solve it. please share your idea or help with this question:
Suppose $C$ is a set of all one-variable computable functions, $C^{(n)}$ is a set of all one-variable computable functions using program with at most $n$ instruction, $C_{(n)}$ is a set of all one-variable computable functions using program with just allowed to use variables $X, Y, Z_1, ..., Z_n$.
Which one is Correct:
a) $ \exists n C^{(n)} = C , \exists n C_{(n)} = C$
b) $ \exists n C^{(n)} = C , \forall n C_{(n)} \subsetneq C$
c) $ \forall n C^{(n)} \subsetneq C , \forall n C_{(n)} \subsetneq C$
d) $ \forall n C^{(n)} \subsetneq C , \exists n C_{(n)} = C$
Answer sheet (2). Any Expert can describe and help idea for solving this difficult contest question?
Edit 1: I think the answer sheet is wrong (b is not correct). There are infinitely many one-variable computable functions, yet depending on our definition of "program", there could only be finitely many programs of length at most $n$. Indeed, "instructions" usually come from a finite set. On the other hand, one could envision a definition of program which includes such statements as $x \gets N$ for an arbitrary $N$ (which count as a single instruction!). If such statements are allowed, the argument in the following paragraph shows that we can in fact do with a finite number of instructions.
On the other hand, for every reasonable definition of program, only finitely many variables should suffice. Indeed, a universal program uses only finitely many variables. So the correct answer is (a) or (d), depending on our definition of "program".
Who can say, why the final answer sheet choose another option? am I wrong?
The explanation in the question seems to be correct - the answer could be (a) or (d) depending on how "instruction" is defined.