Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was reading about counting principle related to TOC. I understand that the set of TMs are countable infinity. I couldn't understand the significance of it. What is its not countable?

share|cite|improve this question
This question is incomprehensible. What is TOC? Presumably theory of computation. The title is not a real question. – Andrej Bauer Jan 13 '13 at 11:31
I agree, it is hard to understand what the actual question is. Please edit your language. – Raphael Jan 14 '13 at 20:36

To expand a bit Luke's answer - the main question is what problems (=languages) can be solved by a computer (=TM).

One might think that any problem can be solved by a computer. But this is not true. The reason is that there are such and such different Turing Machines, and way more different languages. Therefore, there must be a language that no TM can recognize. This language is undecidable, and the "problem" this language represents cannot be solved by any computer. In fact, the vast part of languages are undecidable.

The number of different Turing machines is infinite, but countable ($\aleph_0$), while the number of different languages is infinite of a larger magnitude ($\aleph$, and not countable). See more details on the wiki page for Cantor's diagonal argument, or search this site for related questions.

share|cite|improve this answer

The set of all languages is uncountable, hence there can't be a TM for every language, and there must be languages that aren't recursively enumerable.

share|cite|improve this answer

Each TM can be described by a finite string of symbols (the examples of TMs described in textbooks or elsewhere should give a good idea of how to do it with a limited supply of symbols). Any set of finite-length strings made of a finite set of symbols is countable. To get some non-countable set of machines would require that their description isn't finite, and that defeats the whole purpose.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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