Cheap and Secure Web Hosting Provider : See Now

, ,
Problem Detail:

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.

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.