<p>When I teach the theory of computation, I don't mention uncountability. For me, the hardest part of the course is getting students to go beyond &quot;undecidable because it goes on forever&quot; and get to actual proofs using diagonal arguments and reducibility.</p>

CC BY-SA 4.0
2024-12-30T01:50:41.573Z
2024-12-30T01:50:41.573Z
bburd
<p>I am teaching Turing machines and computability. Among the topics, I cover uncomputability. My first proof of existence for umcomputable languages is through uncountability (before presenting the halting problem and Rice's theroem): there are more languages than algorithms, hence not all languages are computable. To this end I must introduce the notion of uncountability. As a result, I noticed that my students were mixing different concepts. They could write things like &quot;this language is computable since it is countable&quot; that makes no sense. My question(s) is to get insights on how my course could evolve:</p>
<ul>
<li>Is it useful to introduce uncountability for uncomputability? Is the &quot;counting&quot; argument helpful?</li>
<li>Should this counting argument be presented first (as I do)? Or does it make sense to present it after the halting problem for instance?</li>
<li>Do you have ideas to prevent the misinderstanding such as the sentence cited above? (My feeling is that the difficulty is that a language is already a set, countable, and that the counting argument applies to sets of languages, that is sets of sets. This is a typing issue.)</li>
</ul>
<p>Of course there is no definitive answer to any of my questions.  I am more asking about your feelings and experience.</p>

CC BY-SA 4.0
2024-12-31T09:33:45.777Z
I meant language as in formal language theory, so equivalently problems indeed. And per your second comment, the point is exactly that by definition, each language is countable. So forba language countability isn't an argument for (in) computability.
Bruno
<cs-theory><course-design>
Uncomputability and Uncountability
# Uncomputability and Uncountability

(Asked by: username_0 on 2024-12-28)

I am teaching Turing machines and computability. Among the topics, I cover uncomputability. My first proof of existence for umcomputable languages is through uncountability (before presenting the halting problem and Rice's theroem): there are more languages than algorithms, hence not all languages are computable. To this end I must introduce the notion of uncountability. As a result, I noticed that my students were mixing different concepts. They could write things like "this language is computable since it is countable" that makes no sense. My question(s) is to get insights on how my course could evolve:

* Is it useful to introduce uncountability for uncomputability? Is the "counting" argument helpful?
* Should this counting argument be presented first (as I do)? Or does it make sense to present it after the halting problem for instance?
* Do you have ideas to prevent the misinderstanding such as the sentence cited above? (My feeling is that the difficulty is that a language is already a set, countable, and that the counting argument applies to sets of languages, that is sets of sets. This is a typing issue.)

Of course there is no definitive answer to any of my questions. I am more asking about your feelings and experience.

**Tags:** cs-theory, course-design

> **Comments:**
> **username_0**: I meant language as in formal language theory, so equivalently problems indeed. And per your second comment, the point is exactly that by definition, each language is countable. So forba language countability isn't an argument for (in) computability.  

---

## 1 answers

### Answer by username_1 on 2024-12-30. Score: 2

When I teach the theory of computation, I don't mention uncountability. For me, the hardest part of the course is getting students to go beyond "undecidable because it goes on forever" and get to actual proofs using diagonal arguments and reducibility.


---

