Save this video free

CS 181 Lecture 13 -- Fall 2026, UCLA

Eli Jaffe · 1:37:20 · Watch on YouTube

Part of University of California, Los Angeles COM SCI 181. See all 5 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

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

Chapters

0:00 Turing Machines, the Church-Turing Thesis, and Course Logistics
6:00 Encoding a Turing Machine as a Bit String
7:00 The Universal Evaluation Function
9:00 Alan Turing’s Universal Machine and a Python Simulation
14:00 Why a Universal Machine Makes General-Purpose Computing Possible
18:00 Small Universal Machines and the Practical History of Lisp
22:00 Turing-Complete Languages from Magic to LaTeX
28:30 From Universality to Uncomputability
31:20 Defining the Toddler Function by Self-Application
33:30 Why a Program Can Take Its Own Description as Input
37:30 The Naive Toddler Algorithm and the Non-Halting Problem
42:00 The Toddler Function’s Infinite-Loop Edge Case
48:00 Assume a Machine Computes the Toddler Function
52:30 Diagonal Contradiction: N Cannot Match Its Own Output
57:00 Questions About Diagonalization and Program Reasoning
1:09:30 Goldbach’s Conjecture as a Program That May Never Halt
1:14:40 Defining the Halting Function and Its Practical Stakes
1:18:00 Reduction from the Toddler Function to the Halting Function
1:28:50 Reduction Logic and a Second Diagonal Proof of Halting Undecidability

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

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.

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.