I believe the problem stated in title is in P because I can just hardcode $s$ into $<M>$, such that $M()=s$.
However, my real question is, if I want to ensure that the generated $<M>$ is the shortest, is this problem in NP, or even computable?
Formally, define $f: \{0,1\}^*\rightarrow\{0,1\}^*, f(s) = <M>, s.t\quad M()=s \wedge \forall <M'> \in \{0,1\}^{i}, \forall i \in \{1,2,...,|<M>|-1\} , M'()\neq s$.
Edit:
It seems the problem I proposed above is not computable.
What if I add a constraint that the the outputted $M$ must be terminated in $T(|s|) = c_1 |s|^{c_2}+c_3$ steps, where $c_1, c_2, c_3$ are predefined constants.
This problem must be in NP because a NTM could just keep constructing $<M>$ and test it for $T(|s|)$ steps, but is this problem in P?