# Is generating a Turing Machine that output a given string $s$ in NP?

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?

• Mar 8 '18 at 16:50
• Since there are 5-state Turing machines (2-symbol tape) for which it is unknown whether they halt, their output if they do happen to halt is definitely unknown. Maybe it just so happens to be $s$? Mar 8 '18 at 16:50
• Unknown or undecidable, @Arthur ? Mar 8 '18 at 16:51
• @Arthur : Currently, there are 28 5-state TM's with unresolved halting property. Mar 8 '18 at 16:53
• @ThomasAndrews I personally believe it is decidable. 5 states probably isn't enough to reach the hypothesis of Gödel's incompleteness theorems or anything like that. It is known that 8000-state is undecidable, and the true bound might be a bit lower than that, but I think 5 is too low to be undecidable. Whether humanity will ever know is a different question altogether. Mar 8 '18 at 16:55