CS 181 Lecture 11 -- Fall 2026, UCLA
Overview
Eli Jaffe completes the Myhill-Nerode argument that palindromes are not regular, then proves the state lower bound: K pairwise distinguishable strings require at least K DFA states. He introduces Turing machines as finite descriptions with a read-write tape, a movable head, and a finite control, and demonstrates bitwise complement and a tape-marking strategy for computing majority.
Key takeaways
- For any i < j, the prefixes 0^i and 0^j are distinguished by appending 1 followed by i zeros, proving that the palindrome function has infinitely many Myhill-Nerode classes and is not regular.
- If a function has K pairwise incompatible prefixes, any DFA computing it needs at least K states: otherwise the pigeonhole principle puts two prefixes in the same state, making them indistinguishable by every suffix.
- For a regular function, the maximum number of pairwise incompatible strings, its Myhill-Nerode number, equals the state count of a minimal DFA; the full equality is stated but not proved here.
- A Turing machine keeps a finite transition table while gaining unbounded working storage through a tape, with each transition determined by the current state and scanned symbol.
- The one-state complement machine illustrates the Turing machine output convention: it flips each input bit, moves right, then halts at the first blank with the transformed string on the tape.
- Majority can be computed by repeatedly pairing and marking zeros and ones with an auxiliary symbol such as A; an unmatched zero means output 0, while exhausting zeros means output 1.
Chapters
- Eli Jaffe applies the same distinguishability strategy used for majority to show that the palindrome function is not regular.
- For two prefixes 0^i and 0^j with i < j, append the same string, 1 followed by i zeros.
- The resulting string from 0^i is a palindrome, while the one from 0^j is not, so the prefixes are incompatible.
- Every pair 0^i and 0^j with i ≠ j can be distinguished by a suitable appended string.
- The family of zero-only prefixes therefore contains an unbounded number of pairwise incompatible strings.
- A DFA needs a distinct state for each incompatible prefix, so no finite-state DFA can compute the palindrome function.
- The toddler version of Myhill-Nerode says K incompatible strings require at least K DFA states.
- If the number of incompatible strings is unbounded, the required number of states is unbounded, proving nonregularity.
- Jaffe introduces the Myhill-Nerode number as the maximum number of pairwise incompatible strings, with infinity allowed.
- The example function outputs 1 when the number of ones in its input is divisible by 3, and 0 otherwise.
- Three prefixes with different counts of ones modulo 3 can be distinguished by appropriate suffixes.
- No fourth incompatible prefix is possible because the function's behavior depends only on one of three remainders.
- The Myhill-Nerode number gives the exact number of states in a smallest DFA for a regular function.
- Jaffe states this full result but does not prove it in this lecture.
- The lecture instead proves the baby theorem that K mutually incompatible strings force at least K states.
- Assume a DFA computes the function using at most K − 1 states, despite having K pairwise incompatible prefixes.
- By the pigeonhole principle, two prefixes, x_i and x_j, must reach the same DFA state.
- Since a DFA's future behavior depends only on its current state, every shared suffix produces the same result from both prefixes, contradicting their incompatibility.
- Circuits depend on a fixed input size, while DFAs handle unbounded input lengths with a fixed number of states.
- DFAs, NFAs, and regular expressions still cannot compute functions such as majority or palindrome recognition.
- Jaffe frames the next model as a way to retain a finite machine description while relaxing the DFA's computational limits.
- A DFA scans an input once from left to right and cannot revisit earlier symbols.
- Possible upgrades include moving the input head both directions, random access, multiple heads, and read-write access.
- The Turing machine's essential additions are a head that can move along the tape and writable memory.
- A Turing machine has an unbounded tape extending to the right, with a special left-end marker and blank cells for workspace.
- The input initially occupies the tape, and the head begins at the first input symbol.
- A finite set of states tracks the machine's control while the tape stores information that can grow with the computation.
- The tape alphabet includes 0, 1, a start marker, and a blank symbol, with other symbols allowed when useful.
- A transition takes the current state and scanned symbol, then specifies a new state, a symbol to write, and a head action.
- The head can move left, move right, stay in place, or halt; a finite transition table fully describes the machine.
- Computation repeatedly applies the transition rule to the current state and symbol, updating the tape and head position.
- A machine may loop forever, in which case it produces no output.
- When it halts, the output is read from the tape starting at the left marker and ending at the head position.
- Unlike a DFA, a Turing machine can produce an output string of arbitrary length rather than a single accept-or-reject bit.
- The lecture uses a special no-output symbol for a computation that does not halt.
- During the break, Jaffe clarifies that the baby Myhill-Nerode theorem gives a finite state lower bound, while the toddler version uses an unbounded family to prove nonregularity.
- The first example uses one state and the alphabet 0, 1, the start marker, and blank.
- On reading 0, the machine writes 1 and moves right; on reading 1, it writes 0 and moves right.
- At the first blank cell, it halts, leaving the bitwise complement of the input on the tape.
- A function is computed by a Turing machine when the machine's output equals the function's value for every input.
- The output can be an arbitrary-length string, expanding the model beyond single-bit outputs.
- Jaffe returns to majority, a function previously shown impossible for DFAs, and asks how a tape can support the needed counting-like process.
- Jaffe demonstrates a program in a Turing machine simulator, using an extra tape symbol A to mark processed bits.
- The machine repeatedly matches a zero with a one, marking each matched symbol so it is not reused.
- If a zero cannot be matched, it outputs 0; if the search runs out of zeros, it outputs 1, corresponding to at least as many ones as zeros.
- The high-level algorithm scans right for an unmarked zero, marks it A, returns to the start, and searches for an unmarked one.
- If no matching one exists, the input has more zeros, so the machine cleans its scratch marks and returns 0.
- If the scan finds no remaining zero, it cleans the tape and returns 1; otherwise it repeats the matching process.
- Expanding the majority algorithm into a transition table requires separate states for searching, returning to the start, and writing the result.
- Jaffe catches an omitted transition while constructing the table, then stops short of completing every case because the low-level description is tedious.
- The central point is that each step depends only on the current tape symbol and one of finitely many states, yet the writable tape enables substantial computation with a finite machine description.
Transcript excerpt
0:02 All right, people at home, you missed 12 minutes. I apologize. Uh, all we really did was we revisited the proof that the majority function is not regular using toddler NFTt from last class. So, we rewent over this argument and now we are applying the same arguments to this pal function. I'm trying to show that the pound function is not regular using toddler >> 17. All right, let's come back together
0:57 and who has an idea? So, as a reminder, what we need, we need a set of n mutually incompatible string meaning they're not the same as each other under this ephobation like this is little mutually incompatible drink. So, what could be a jumping off point? >> Could be anything.
1:51 I mean, there's one really low hanging piece of fruit we've already seen recently. Okay. Who's who's who's got some good short-term memory? Yes. >> Sorry, I'm having a little trouble hearing you. I heard all ones and then all zeros and then something at the end. in the space they see. >> Okay. So, one string that's all zeros, one
2:39 string that's all ones. That's two strings. >> Precise. >> So, okay. I like there's some good ideas in here though. Uh, yes. >> Sorry. >> So, the question is we need to come up with a set of end strings. These end strengths should all be not equal to each other under this relationship. Meaning if I pick any two of them, there should be something I can append to the end of both of them. Same string to the end of both of them such that one is a palendrome and one isn't. That's our goal. >> Risa idea. Oh my god. See, somebody remembers what
3:29 we did five minutes ago. We could try
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, Eli Jaffe.