That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language?

Similarly, can you recognize or decide if a Turing Machine has an uncountably-infinite language?

  • 4
    $\begingroup$ Hint for the first part: diagonalization / Rice's theorem. Hint for the second part: all languages are countable. $\endgroup$ – Yuval Filmus May 5 '14 at 23:41
  • $\begingroup$ Thanks for the hints, but could you elaborate a bit more? 1) How can we use diagonalization to prove part 1 (we didn't learn Rice's Theorem in class) and 2) Suppose a language has 3 characters in it. Then wouldn't the size of the language be 3^N (where N refers to the natural numbers), which is uncountably infinite? $\endgroup$ – user3605801 May 6 '14 at 0:12
  • $\begingroup$ ^ What makes languages countably infinite is that they only contain finite strings. In this light, it doesn't matter how large $\Sigma$ is; $\Sigma^*$ will be countably infinite, not uncountable. $\endgroup$ – Guildenstern May 6 '14 at 0:18
  • $\begingroup$ Ok thanks that makes sense; I think I buy part 2. But what about part 1? I'm guessing it's both unrecognizable and undecidable because we cannot possibly test all strings. $\endgroup$ – user3605801 May 6 '14 at 0:25
  • 1
    $\begingroup$ @Guildenstern Assuming $\Sigma$ is countable, but that's of course the usual assumption. ;) $\endgroup$ – Raphael May 6 '14 at 6:46

To elaborate somewhat on Yuval's comment:

(1) Some languages have an infinite number of strings, some do not. This makes the property non-trivial, and Rice's theorem says that recognizing whether the language of a Turing Machine has a non-trivial property is undecidable. This problem is undecidable.

(2) All languages are countable; none are uncountable. This makes the property trivial. Deciding whether the language of a TM has a trivial property is always decidable: if it's a property all languages have, then answer yes; if it's a property no languages have, answer no.

(A word of general caution, though it doesn't apply here. Rice's theorem applies only to properties of languages themselves, not properties of the TMs that might accept them. This is an important distinction. Rice's theorem only works for properties that have to do with the language and strings it contains.)

For reference: Rice's Theorem

  • $\begingroup$ Don't know what's Rice theorem but I thought immediately about The Halting Problem XD. $\endgroup$ – Luis Masuelli May 6 '14 at 16:14
  • 1
    $\begingroup$ Even worse, the language of TM descriptions $\langle X\rangle$ for which $L(X)$ is infinite is unrecognizable. $\endgroup$ – Rick Decker May 8 '14 at 0:54
  • $\begingroup$ Given a solution to the halting problem in hand, I still can't see how to solve it. (In general Rice's theorem means less than we like because we can avoid all of its bad implications by constraining the domain to Turing machines that halt.) $\endgroup$ – Joshua Oct 19 '15 at 16:14

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.