I am going through undecidability of TM and found this question

$L=\left \{ \left \langle M \right \rangle |M\ is\ TM \ and \ number\ of\ strings\ in\ the\ language\ \ is\ prime\right \}$

I think it is decidable as number of strings in the language is prime ,i.e , 2,3,5,7,11,13,17,............. It seems to me like it is accepting all the strings.

If it has accepted 17 strings, then it must have accepted 12 strings, 14 strings, 16 strings and so on. Actually i am not getting from where to start.

Can anyone provide legal explaination of what is actually happening here ?

  • $\begingroup$ an encoding of a TM $M$ is in the language if the number of words in $L(M)$ is a prime number. That is, if it accepts exactly a prime number of strings, not "at least" a prime number of strings. Are you familiar with undecidable languages, and techniques for proving undecidability? What have you tried? $\endgroup$ – Shaull Nov 3 '16 at 12:04
  • $\begingroup$ Here are some questions for you to ponder: This decision problem is a problem about $L(M)$, where $M$ is a Turing machine. Is there a general method for predicting if the total number of strings that can be accepted by $M$ is a prime number? If we could indeed predict this for any Turing maching out there (remember, $\langle M \rangle$ is the parameter of the problem, it is not fixed in advance), given a description of it, could we then use this to find a decision procedure for another prediction problem for Turing machines? Do prediction problems for Turing machines tend to be decidable? $\endgroup$ – Hans Hüttel Nov 3 '16 at 12:14
  • 3
    $\begingroup$ You can use Rice's theorem, or a direct reduction from the halting problem, to show that $L$ is undecidable. $\endgroup$ – Yuval Filmus Nov 3 '16 at 12:25
  • $\begingroup$ @YuvalFilmus, yes I am successful in the reduction part. It is undecidable but I am still struggling for determining RE or not, as i think it is non monotonic property also ? $\endgroup$ – Garrick Nov 3 '16 at 17:55
  • 1
    $\begingroup$ Try to prove that it's RE. If you fail, it probably isn't. $\endgroup$ – Yuval Filmus Nov 3 '16 at 18:48

Consider a problem 'A' which is undecidable. If 'A' is reducible to another problem 'B', then problem 'B' is undecidable.

Consider following two statements:

p: Turing machine halting problem is undecidable.
s: A given Turing Machine 'M' reaches a state 'q' on reading input 'w'.

If we can modify statement 'p' in such a way that the answer to 's' will be answer to 'p', then we can say problem 's' ( statement 's' ) is undecidable.

Also note that I will be using a term "Dead Configuration" to mean the Turing machine is in a state from which no further transitions is defined i.e, a Turing machine halts because of a dead configuration.

Modified version of 'p': A Turing machine halts only at state 'q'.

That is, whenever a Turing machine reaches a dead configuration, we will make a transition to 'q'.
Modified version pf 'p' is undecidable, which means it is undecidable that a Turing machine reaches a state 'q' on reading any input.
Hence, problem 's' is also undecidable.

On the same lines statement 's' can be modified to prove that the problem, "Turing machine will accept a string" is undecidable.

Hence, if the problem: "whether a string is accepted by a Turing machine" is undecidable then the problem of counting the number strings in a language will also be undecidable.

  • $\begingroup$ Is this non monotonic property ? $\endgroup$ – Garrick Nov 3 '16 at 14:00
  • $\begingroup$ @Willturner Yes $\endgroup$ – Akash Mahapatra Nov 3 '16 at 16:09

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.