4
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ Hint for the first part: diagonalization / Rice's theorem. Hint for the second part: all languages are countable. $\endgroup$
    – Yuval Filmus
    Commented May 5, 2014 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
    Commented May 6, 2014 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
    Commented May 6, 2014 at 0:18
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Commented May 6, 2014 at 6:45
  • 1
    $\begingroup$ @Guildenstern Assuming $\Sigma$ is countable, but that's of course the usual assumption. ;) $\endgroup$
    – Raphael
    Commented May 6, 2014 at 6:46

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Don't know what's Rice theorem but I thought immediately about The Halting Problem XD. $\endgroup$
    – Luis Masuelli
    Commented May 6, 2014 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
    Commented May 8, 2014 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
    Commented Oct 19, 2015 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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