Take the 2-minute tour ×
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.

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|improve this question
3  
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
1  
I agree, it is hard to understand what the actual question is. Please edit your language. –  Raphael Jan 14 '13 at 20:36
add comment

3 Answers 3

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.