Cheap and Secure Web Hosting Provider : See Now

[Answers] Turing machine enumerator

, , No Comments
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.

Asked By : vukov

Answered By : jmite

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53507

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback