Would you say that the following problem is undecidable? $$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$ My intuition says that this must be undecidable, and I want to try to reduce it from the emptiness problem for Turing Machines. If we can tell whether or not a TM accepts 14 words, then we should be able to tell if it accepts 0. Since we know EMPT is undecidable, I have been trying to do reduce EMPT to this problem, but I am not sure exactly how to do it.

Can anyone confirm if this is actually a valid starting point, and if it is, any hints on how to formulate a formal reduction?

  • 1
    $\begingroup$ Are you allowed to use/have you seen Rice's Theorem? If you're allowed to use it, then the result follows pretty quickly, however, if you haven't seen it, it may be worth looking at, as it gives a template for building the proofs in the style David Richerby suggests in his answer. $\endgroup$ – Luke Mathieson Nov 10 '18 at 23:29
  • $\begingroup$ No, I prefer not to use Rice's Theorem. I want to become better at reductions. $\endgroup$ – Johnny Pandeleo Nov 11 '18 at 0:19
  • $\begingroup$ You should take a look at the proof of Rice's theorem then. It gives a general structure for constructing reductions like this, which gives you a handy tool when you want to do them. $\endgroup$ – Luke Mathieson Nov 11 '18 at 10:24

Your intuition is correct. Probably you can reduce emptiness (or maybe its complement) to this language but it's not the way I'd do it. Instead, think about how you prove that emptiness is undecidable.

You want to know if $M$ halts on input $w$ so you produce a TM that accepts everything if $M$ accepts $w$ and rejects everything if $M$ rejects $w$. A slight modification of that proof will show that your language is undecidable.

  • $\begingroup$ Thanks. So for the emptiness problem we assume we have a decider R for it. We then construct an algorithm S (to solve acceptance problem) that on input $\langle M, w\rangle$ creates a modified version of $M$, $M'$, which only accepts w. Now it runs R on input $\langle M' \rangle$. If R accepts, then the language must be empty, so S rejects. If R rejects, we know that $M'$ only recognises w, so S must accept w. Now I am wondering how I modify this to my problem. If my R accepts, that means the language of $M'$ is made up of exactly 14 strings, if it doesn't it means it is not made up of 14. $\endgroup$ – Johnny Pandeleo Nov 11 '18 at 0:50
  • $\begingroup$ Do I need to modify $M'$ so that it accepts the 14 strings ? But this wouldn't make sense because they are not known. Basically, I am confused because if R accepts, I dont see how this solves the acceptance problem. $\endgroup$ – Johnny Pandeleo Nov 11 '18 at 0:57
  • 1
    $\begingroup$ Ah -- I was thinking of a different proof. The one I had in mind, you convert $\langle M,w\rangle$ into a machine that replaces its input with $w$ and then simulates $m$: that either accepts all inputs or rejects all inputs. So, add a step that ensures it either accepts 14 inputs or no inputs (you get to pick what those inputs are, so they may as well be $1$, $11$, ..., $11111111111111$ or something convenient.) $\endgroup$ – David Richerby Nov 11 '18 at 0:59
  • $\begingroup$ I don't quite understand that proof. So you are again simulating $M$ on input $w$, but you have defined this different machine such that it either accepts all of its inputs or rejects all of them? How does this work? $\endgroup$ – Johnny Pandeleo Nov 11 '18 at 1:05
  • $\begingroup$ The simulating machine $M'$ erases its input, replaces it with $w$ and then runs $M$. So, whatever input it gets, it ignores that and just computes $M(w)$. So, if $M$ accepts $w$, $M'$ accepts every input; if $M$ rejects $w$, $M'$ rejects all inputs. So, to decide whether $M(w)$ halts, you just need to check if $M'$ accepts the empty language. $\endgroup$ – David Richerby Nov 11 '18 at 1:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.