Turing machine enumerator

Question

As the number of Turing Machines is countably, we can create some list of them and number them 1, 2, 3,... Suppose turing machine k computes some function $f_k$. Is there a turing machine S that can computer $f_k(k)$?

It seems like there should be, as I am fairly confident that you can write such a program in a turing-complete language. However, I am having a hard time seeing how an $n$ state turing machine (if S is n states) could compute every function computed by an $n^2$ state turing machine, for example.

Answer 1

Indeed, there is such a Turing Machine. First, realize that it's computable to convert any integer $k$ into the $k$th Turing Machine description, just by enumerating them. Then, once we have the Turing Machine description, we can use a Universal Turing Machine to compute the function described.

The key is that, while there are less states in the $n$-state machine than in one with $n^2$, any number of additional states can be encoded on the tape of the Turing Machine. So there's no limit to the amount of information we have when computing the $k$th function, since an arbitrary amount of information can be encoded on the tape.

Answer 2

Universal Turing Machine for every model has finite number of states, but it can simulate any Turing Machine with arbitrary large number of states. This is because all the state information of the simulated machine (actually the whole configuration) is kept into the tape.

So it is not the case of how finite states can hold potentially very large information. It is rather how (finite state + infinite tape) holds (very large number of states + infinite tape). Basically there is no problem with storing $(n^2 + \infty)$ information in $(n+\infty)$ space.

And there are two ways to enumerate Turing Machines. Easier way out is just take binary representation of $i$ as Turing Machine $M_i$. If it is a valid representation it is okay, if it is not, we shall assume it to be a Turing Machine that does not accept any input. The Universal Turing Machine will also honor this fact.

But if we are given a fixed representation and need to generate $i$'th valid Turing machine then we need to do it in hard way. We need to generate $\alpha_{M_i}$ the representation of $M_i$ one by one after checking if it is a valid Turing Machine. In this case the Universal Turing Machine will always get a valid representation of a Turing Machine.