My question (in brief) is:
(1) Given an encoding for a TM M (i.e. given $\langle M \rangle$, how do we simulate the actual machine M in a computable manner? and,
(2) Given the actual machine M, how do we get it's encoding (i.e. $\langle M \rangle$) in a computable manner?
I've asked this question before to my professor, and based on the response I'm clearly not understanding something. So I try to illustrate my question with an example:
Suppose $M_0$ is the TM: $Q = \{q_1, q_0\}$ , $δ(q_1, \_) = (q_0, \_ , R)$ where $q_0$ is a halting state and $q_1$ is a starting state, and the tape alphabet is $\{1, B \}$. Then the function computed by $M_0$ is $f_0(x) = x + 1$. And let a description of $M_0$ as a list, (denoted as $\langle M_0 \rangle$) be $11 BBBBB 1BBB1 BBBBB 11B11$ (here $11$ denotes there are 2 states in Q, $1BBB1$ denotes $δ(q_1, B) = (q_0, B, R)$, $11B11$ denotes $δ(q_1, 1) = (q_0, 1, R)$ and $BBBBB$ is used to separate two entries in a list).
Now $M_0$ is a machine i.e. it has a single tape, a tape head which has some states, and based on what is written on it's tape, this machine starts computing something.
But $\langle M_0 \rangle$ is essentially a number (here it's a list of values). How does one go from $\langle M_0 \rangle$ to $M_0$ in a computable manner, and also vice versa.
Some more context as to where this question arises from?
It actually arises from the proof of the s-m-n theorem (let's take m = n = 1 here). So the goal is given a partial computable function g of two variables we are trying to find a total computable s which satisfies $\phi_{s(x)}(y) = g(x,y) $ where $\phi_e$ is the function computed by the eth Turing machine on the list of all TM's according to the enumeration theorem. Clearly as we have g is partial computable, we have a TM to compute $\phi_{s(x)}$. From here, the book (and professors and everyone else) says that we compute the index s(x) using the converse of the enumeration theorem - but: the converse of enumeration theorem says that there is a p.c function which on input $\langle \phi_{s(x)} \rangle$ outputs $s(x)$. Here we only have the actual TM $\phi_{s(x)}$. Is there some p.c. function which on input $\phi_{s(x)}$ gives $\langle \phi_{s(x)} \rangle$ - then this statement would be true.
Also part (1) arises from, when we use a TM M to compute another TM M'? We are only given the number $\langle M \rangle$ - so how do we simulate the actual machine $M$?
