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$.


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?

  • $\begingroup$ Related: en.wikipedia.org/wiki/Kolmogorov_complexity $\endgroup$
    – parsiad
    Mar 8 '18 at 16:50
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Arthur
    Mar 8 '18 at 16:50
  • $\begingroup$ Unknown or undecidable, @Arthur ? $\endgroup$ Mar 8 '18 at 16:51
  • $\begingroup$ @Arthur : Currently, there are 28 5-state TM's with unresolved halting property. $\endgroup$ Mar 8 '18 at 16:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arthur
    Mar 8 '18 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.