# If set of TM's is not countable?

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?

-
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.

-

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.

-

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.

-