Save this video free

CSCD 420 Nov 10 2026

Chris Cain · 51:03 · Watch on YouTube

Part of Eastern Washington University CSCD 420. See all 32 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

Overview

Chris Cain explains countability through enumeration procedures, showing how the rational numbers can be listed while Cantor's diagonalization proves that even the real numbers between 0 and 1 cannot. He connects these ideas to computation by showing that Turing machines have countable descriptions, then introduces linear bounded automata and demonstrates how one can recognize strings whose lengths are factorials using only input-bounded tape space.

Key takeaways

Chapters

0:00 Reviewing Countability and Setting Up the Rational-Number Question
1:55 Defining Rational Numbers and the Enumeration Challenge
5:33 Enumerating Rational Numbers by Diagonals
10:00 Why Finite Decimal Listings Miss Real Numbers
15:00 Cantor's Diagonalization Proves the Reals Are Uncountable
22:00 Enumeration Procedures Require Fair Progress
29:00 Why Turing Machines and Algorithms Are Countable
31:00 Restricting Turing-Machine Memory to Define Language Classes
35:41 Designing a Linear Bounded Automaton for Factorial-Length Strings
40:21 Testing Factorials by Repeated Division on Bounded Tape
48:13 Comparing Linear Bounded Automata with Pushdown Automata

Keep these chapters and the full searchable transcript in your own library.

Transcript excerpt

0:03 Time for us to get started. And this this is going to be interesting. This is the lowest head count we've had in here, I think. So, I hope you are being feeling especially outgoing today. I'll need a little bit of interaction as we as we go through things, which means that on average, you need to be 1/8 of the interaction. Don't pray. They must uh perhap students here to fill the void. Excellent. All right. We have an assignment due on Thursday. I will have office hour availability after this class and from about 1 to 2 this afternoon, but I will

0:52 unfortunately have to cut off at 2. Last time we were going over countable and uncountable sets as the last thing we were we were talking about. And we started out by giving the logic for why the set of all integers was countable. And we ended up being able to come up with a function that mapped the positive integers onto all integers. And since the set of positive integers is countable, then we could conclude that the set of all integers was countable. And in general, that is how we're going to prove countability. If we can map a function between a countable set and another countable set so that every element of one set can be reproduced,

1:40 the target set can be reproduced by the query set. Then we are good. So I'm going to really challenging one to determine whether if it is if it's countable or not countable uncountable. We will see what we come up with. So how about the set of rational numbers? First we should define them. What is a rational number? >> Clearly a number that can be number that can be reasoned with. It's a

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Chris Cain.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.