Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Are finitely many statements resp. variables sufficient to compute every function?

, ,
Problem Detail:

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, 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 see in refrences book, \$Y\$ is output variable, \$X\$ is input and \$Z_1, ...., Z_n\$ is local variable by program P. can see in p. 25 ref

#### Answered By : Yuval Filmus

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, \$X_1\$ and \$X_2\$, and simulates the one-input program encoded by \$X_2\$ on the input \$X_1\$. 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 \$X_2\$ 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 \$X_2 \gets 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 \$X_2 \gets m\$ for the correct value of \$m\$. So (a) is correct.

Case 3: There are infinitely many instructions, but \$X_2 \gets 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.