I prepare for local complexity contest and review some old Interview questions b
ID: 647151 • Letter: I
Question
I prepare for local complexity contest and review some old Interview questions 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,Z1,...,Zn.
Which one is Correct:
a) ?nC(n)=C,?nC(n)=C
b) ?nC(n)=C,?nC(n)?C
c) ?nC(n)?C,?nC(n)?C
d) ?nC(n)?C,?nC(n)=C
Answer sheet (2). Any Expert can describe and help idea for solving this difficult contest question?
Explanation / Answer
Your example sheet is wrong (assuming (2) means (b)). The answer is ambiguous, because it depends on the notion of "program", or rather "instruction".
The main trick one has to use here is the existence of a universal program. A universal program takes two inputs, X1 and X2, and simulates the one-input program encoded by X2 on the input X1. In order to implement any one-input program, all we have to do is to supplement the universal program with code that sets the value of X2 to one encoding our desired program.
Using this trick, we see that if the universal program uses n variables, then in fact every computable function can be implemented using n variables. This means that (b) and (c) are wrong. In order to see whether (a) or (d) are correct, we need to consider three cases.
Case 1: The instruction set are finite; there are finitely many instructions. In that case, there are only finitely many programs of length n. Since there are infinitely many computable functions, there is no n such that all computable functions can be implemented using n instructions. So (d) is correct.
Case 2: There is an instruction X2?m for arbitrary m (or more generally, we can implement this operation using a bounded number of instructions). In this case, given universal program with n instructions, we can simulate any program using only n+1 instructions, by prepending the instruction X2?m for the correct value of m. So (a) is correct.
Case 3: There are infinitely many instructions, but X2?m cannot be implemented using a bounded number of instructions. In this case, assuming variable assignment can be implemented using a finite number of instructions, in particular we cannot implement the constant function m using finitely many instructions. So (d) is again correct.
Note that Case 1 is actually a subcase of Case 3.