CSCD 420 Nov 10 2026
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
- A set is countable when its elements can be enumerated so that every member appears at some finite index; the enumeration may continue forever.
- Diagonal traversal enumerates rational numbers because each fraction has a finite numerator-denominator coordinate, even though simple row-by-row traversal would get stuck.
- Cantor's diagonalization defeats any proposed list of real numbers between 0 and 1 by constructing a real that differs from the entry at every corresponding digit.
- Turing machines are countable because each has a finite binary description, and valid descriptions can be filtered from an enumeration of binary strings.
- A linear bounded automaton uses tape space proportional to the input, bounded by end markers; with two tracks it can test factorial input lengths through repeated divisibility checks.
- Linear bounded automata recognize some non-context-free languages, placing them above nondeterministic pushdown automata but below unrestricted Turing machines.
Chapters
- The class revisits the proof that the integers are countable by mapping positive integers onto all integers.
- An assignment is due Thursday, and Chris Cain offers office hours after class and from about 1 to 2 p.m.
- A rational number can be represented as a fraction with an integer numerator and a nonzero integer denominator.
- The class considers whether fractions can be listed despite there being infinitely many between any two distinct rational values.
- Any valid enumeration must eventually output every rational number, not merely produce values arbitrarily close to it.
- Cain arranges numerators and denominators in a two-dimensional grid and traverses the cells diagonally, rather than completing an infinite row or column.
- The diagonal traversal reaches every numerator-denominator pair; invalid zero-denominator entries can be skipped and equivalent fractions may appear more than once.
- Negative rationals can be included by adding negative counterparts to the enumeration, and zero can be handled separately.
- Listing decimal strings by increasing finite length reaches every terminating decimal but never reaches an infinite decimal expansion.
- The decimal 1/3, as well as irrational examples such as pi and e, cannot be output as a finite decimal string.
- Cain introduces Cantor's diagonalization as a way to prove that no enumeration can include all real numbers between 0 and 1.
- Assume an indexed list contains every real number between 0 and 1, with each entry written as an infinite decimal expansion.
- Construct a new decimal by changing the first digit of entry 1, the second digit of entry 2, and so on, for example by adding 1 modulo 10.
- The constructed number differs from every listed number at that number's corresponding digit, contradicting the claim that the list is complete.
- The proof shows that the reals form a larger infinity than the positive integers or the integers.
- An enumeration procedure needs a first output, a successor rule, and a proof that every member appears at some finite index.
- For strings over the alphabet {A, B, C}, alphabetical ordering alone gets trapped among A-only strings and never reaches strings containing B or C.
- Ordering strings first by length and then alphabetically eventually reaches every finite string, even though the procedure itself never terminates.
- A Turing machine can be represented by a finite binary description, so candidate descriptions can be enumerated as binary numbers.
- Testing each description for validity and retaining valid ones yields an enumeration of Turing machines.
- The argument depends on finite descriptions over a finite alphabet and shows that the set of algorithms is countable.
- Adding features such as multiple tracks, a stay-put move, or one-way movement does not necessarily increase the languages a Turing machine can recognize.
- A fixed, finite tape bound gives only finitely many configurations, connecting bounded memory to finite-state machines.
- A linear bounded automaton restricts its tape to the input span, marked by unrewritable left and right end markers, while allowing a finite number of tracks.
- The exercise is to recognize the language of strings a^n! using tape space no greater than the input length.
- The proposed machine uses one track for the input A symbols and a second track to store a current divisor in unary.
- The machine repeatedly checks whether the remaining number of A symbols is divisible by successive integers, marking removed A symbols as X.
- For an input of 120 A symbols, the machine divides successively by 2, 3, 4, and 5, leaving 60, 20, 5, and finally 1.
- The second track counts the current divisor, while the machine skips X symbols and marks the appropriate A symbols during each pass.
- The machine accepts when the repeated divisions reach exactly one with a complete pass; a non-exact division or an incorrect remainder leads to rejection.
- The procedure uses only the input-sized tape and two tracks, with end markers preventing movement beyond the available space.
- Cain states that linear bounded automata can recognize languages such as {a^n!}, which is not context-free by the context-free pumping lemma.
- This makes linear bounded automata more powerful than nondeterministic pushdown automata, but less powerful than unrestricted Turing machines.
- The class ends with the automata hierarchy and plans to return to applications of the theory later in the week.
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.