CS 181 Lecture 13 -- Fall 2026, UCLA
Overview
Eli Jaffe develops the consequences of encoding Turing machines as data: a universal Turing machine can simulate any encoded machine, while diagonal self-reference proves that some functions cannot be computed. He defines a “toddler” function that inverts a machine’s output on itself, uses its uncomputability to establish the uncomputability of the halting function by reduction, and introduces a second diagonal proof to complete next lecture.
Key takeaways
- A universal Turing machine can simulate any encoded Turing machine, which replaces task-specific hardware with a general-purpose computer that runs different programs.
- Turing completeness requires only enough expressive power to simulate a universal machine, which is why systems such as Minecraft, Magic: The Gathering, and TI-84 calculators can support general computation.
- The toddler function is uncomputable because applying its assumed implementation to its own description forces its output to be the opposite of what it must produce.
- A universal algorithm for deciding whether any program halts on a given input cannot exist; this is a mathematical impossibility, not merely a problem of slow execution.
- Reduction transfers uncomputability: if a hypothetical solver for the halting function could compute the uncomputable toddler function, then the halting function must also be uncomputable.
Chapters
- Jaffe recaps the claim that Turing machines can simulate modern programming languages, invoking the Church-Turing thesis as a foundational principle rather than a formal theorem.
- The “best of both worlds” approach uses Python to demonstrate computability and Turing machines to reason about limitations.
- Exam 1 averaged about 18.5 out of 25, with a standard deviation of 3.5; exam 2 was scheduled for Monday and covered lectures 9 to 14.
- A Turing machine is encoded by traversing its transition table row by row and representing the description as a bit string, denoted with bracket notation around the machine name.
- Treating machine descriptions as data makes it possible to pass a program’s representation into another program.
- Jaffe identifies universality and uncomputability as the two major results to derive from this code-as-data idea.
- The evaluation function takes an encoded Turing machine and an input, then returns the machine’s output if it halts.
- If the encoded machine does not halt on its input, the evaluator also does not halt.
- The key result is that this universal evaluator is itself computable by a Turing machine.
- Alan Turing showed in 1936 that a universal machine can evaluate encoded machines; Jaffe demonstrates the idea with high-level Python-style pseudocode.
- The simulator stores the tape, current state, and head position, repeatedly applies the transition function, writes symbols, and moves the head until the simulated machine halts.
- Turing’s original paper specifies the universal machine through a detailed transition table, while the lecture uses the Church-Turing thesis to avoid reproducing every transition.
- A universal machine replaces the need to build separate hardware for tasks such as addition, multiplication, and palindrome recognition.
- Jaffe highlights Turing’s prediction that engineering specialized machines would give way to programming a universal one.
- The universal-computer idea makes software engineering possible: users can change a program rather than redesign the hardware.
- Jaffe notes that universal Turing machines can have as few as 25 states and four symbols.
- Lisp began as a theoretical way to describe universal computation, including a meta-circular evaluator that evaluates Lisp functions.
- Graduate student Steve Russell implemented the evaluator in assembly, turning the theoretical idea into a practical system that could run Lisp programs.
- A programming language is Turing-complete if it can simulate a universal Turing machine.
- Examples discussed include Magic: The Gathering, Minecraft, Minesweeper, PowerPoint, graphing calculators such as the TI-84, and LaTeX.
- These examples illustrate that systems designed for games, presentations, or document preparation can accidentally provide enough state and transitions for general-purpose computation.
- Encoding programs as data supports universal simulation, but it also enables constructions that expose the limits of computation.
- Turing’s 1936 work showed that some functions cannot be computed by any Turing machine.
- Under the Church-Turing thesis, these limits apply to any computation achievable by physical means, not just to one programming language.
- The toddler function takes an encoded machine and returns the opposite of that machine’s output when run on itself.
- It returns 1 when the machine on itself outputs 0, and returns 0 when the machine outputs 1 or fails to halt.
- Jaffe emphasizes that running a program on itself is valid because a program’s encoded description is also a string that can be supplied as input.
- Jaffe uses an “ecount” program, which counts the letter E in a string, to show how a program can process the text that describes itself.
- The example’s source description contains four instances of the letter E, so applying ecount to its own representation has an ordinary, well-defined result.
- Self-application supplies the input needed for the toddler function’s diagonal construction.
- The obvious implementation evaluates machine M on its own description and flips the result.
- That implementation fails when M(M) runs forever: the proposed evaluator becomes trapped and cannot return the toddler function’s required output of 0.
- A simple infinite-loop program demonstrates the mismatch between the toddler function’s specification and the naive algorithm’s behavior.
- For the trivial-loop machine, the toddler specification says to return 0 because the machine does not output 0 on itself.
- The naive implementation instead waits forever while evaluating the trivial loop, so it returns nothing.
- This counterexample disproves the obvious implementation but does not yet prove that every possible implementation must fail.
- Jaffe begins a proof by contradiction: suppose a Turing machine N computes the toddler function on every machine description.
- Because N is assumed to compute toddler, N on any input must match the specified toddler output for that input.
- The proof tests this assumption on N’s own description, using self-reference to force a contradiction.
- If N(N) outputs 0, the toddler definition requires toddler(N) to output 1, contradicting the assumption that N computes toddler.
- If N(N) outputs 1, the toddler definition requires toddler(N) to output 0, producing the opposite contradiction.
- Since N must halt with a bit if it computes toddler, these two output cases show that no such machine N exists.
- Jaffe clarifies why both output cases are needed: ruling out N(N) = 0 alone would still leave open the possibility that N(N) = 1.
- The class discusses how non-halting behavior affects function definitions and whether changing the toddler function’s cases would alter the proof.
- Jaffe identifies reasoning about a program’s input-output behavior as a recurring source of difficulty in computability results.
- The Goldbach conjecture claims every even number is a sum of two primes; examples include 24 = 17 + 7 and 32 = 19 + 13.
- A short brute-force program checks successive even numbers, searching each number for a pair of primes that sums to it.
- If the conjecture is false, the program eventually finds a counterexample and halts; if it is true, the search continues indefinitely.
- The halting function takes a machine description and an input, returning 1 if the machine halts and 0 otherwise.
- The Goldbach-search example shows how even a short program’s halting behavior can hinge on a difficult mathematical question.
- Jaffe explains that IDE warnings and code-analysis tools can catch particular patterns, but no algorithm can decide halting for every possible program and input.
- To prove halting uncomputable, Jaffe assumes a hypothetical halting procedure and uses it as a subroutine to compute the already-proven-uncomputable toddler function.
- The reduction first asks whether M halts on itself; if not, it returns 0 immediately instead of getting trapped.
- If M(M) does halt, the procedure evaluates M(M) and flips the result, so a halting algorithm would make toddler computable, a contradiction.
- A reduction from problem A to problem B means that an algorithm for B can be used to solve A; therefore, if A is uncomputable, B must also be uncomputable.
- Jaffe starts a direct proof by contradiction, supposing a halting procedure exists and defining a machine called “Can’t Solve Me.”
- “Can’t Solve Me” loops forever if its input machine halts on itself and returns 0 otherwise; Jaffe leaves the resulting self-reference contradiction for the next lecture.
Transcript excerpt
0:02 All right, let's get started. Hello everybody. Happy week seven, which was crazy. Um, let's pick it up from last time. So, where were we at in our story of theoretical computer science? Well, we've been talking about touring machines because we've been basically building up to this the whole year, right? We've talked about all these different models of computation, what they're good at, what they're bad at, their limitations, and finally we kind of extended DFAs into Turing machines and thus far have explored some things that they can do that previous modelation could not. And we've made some bold claims, most of
0:51 them unproven up to this point. [clears throat] And one of those claims was that basically touring machines can do everything that all of our modern programming languages can do. And so we kind of talked about touring machines as this programming language that though very simple can do all things that we're used to. We also talked about one of the implications of this being this have our cake and eat it two principle or as I like to call it the best of both worlds. Um, anybody do their homework? Watch an episode of Anna Montana. Everybody fails. Everybody fails the class. that um this idea that because touring machines are equivalent to modern
1:41 programming languages when we're trying to prove that things are computable by touring languages we can take the easy route and just show that they're computable in a high level language like Python and if they're we're trying to show something that's not computable by turning machines we can refer to the more simplistic turning machine one getting to do it kind of both ways And then we built up into the church touring thesis which this was this kind
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.