Save this video free

CS 181 Lecture 14 -- Fall 2026, UCLA

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

Part of University of California, Los Angeles COM SCI 181. See all 6 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 closes the Turing-machine unit by proving the halting problem uncomputable, introducing computable many-one reductions, and reducing HALT-ON-ZERO to NOT-EMPTY and EXACTLY-ONE. He connects these examples to Rice's theorem: every nontrivial property determined solely by a program's input-output behavior is uncomputable, limiting tasks such as general program equivalence and software verification.

Key takeaways

Chapters

0:00 Lecture 14 Opens with the Final Turing-Machine Unit
3:16 Exam 2 Scope, Study Advice, and Upcoming Deadlines
8:43 Why the First HALT-Based Reduction Fails
15:40 A Self-Referential Contradiction Proves HALT Is Uncomputable
22:55 From HALT and the Toddler Function to More Impossibility Results
25:03 Many-One Reductions Transform Inputs Between Problems
30:38 Why a Reduction Must Itself Be Computable
35:53 Many-One Reductions Versus Turing Reductions
38:25 Setting Up the Reduction from HALT to HALT-ON-ZERO
42:59 Hard-Code M and x into a Program That Ignores Its Input
49:35 Why a Halting Oracle Is Not the Same as Running the Program
57:09 Verifying the HALT-ON-ZERO Reduction
1:02:58 Clarifying Program Descriptions, Inputs, and Reduction Direction
1:09:13 NOT-EMPTY Asks Whether a Program Ever Outputs One
1:14:26 Reduce HALT-ON-ZERO to NOT-EMPTY
1:19:40 EXACTLY-ONE Counts Inputs That Produce Output One
1:25:51 Modify the NOT-EMPTY Construction for EXACTLY-ONE
1:32:36 Uncomputable Program Equivalence and Software Verification
1:35:19 Semantic Properties and Rice's Theorem
1:39:00 Rice's Theorem Rules Out General Checks of Program Behavior
1:43:33 Uncomputability Beyond Programs and the Move to Grammars
1:47:07 Questions on Correctness, Exam Preparation, and Key Functions

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

Transcript excerpt

0:04 All right. Hello everybody. Happy almost Thanksgiving. Uh I hope everybody's as excited that I am. I don't have to work next week, at least in my full-time job. I'm still looking to teach you guys obviously. Um let's get back into the business. Very exciting. Today's our last lecture of material for exam 2. It's also our last lecture on touring machines. So, we're going to close it all out with a bang. And as a reminder, last time we did some pretty cool stuff. So we established universality of touring machines meaning they can sort of because we can create one universal touring machine that can compute anything that any other touring

0:51 machine can compute which again as far as vendors stand is everything that we can compute and we paired that with some cool results in uncomputability. really deeply surprising paradoxical results that there's some things which are very normal, easy to state, tractable, applicable, you know, things we would like to compute that just don't seem to be possible. Uh so in particular, we talked about the toddler function which was our first step and felt a little bit contrived. Uh but then we move past that and we talk about the halting problem which really is valuable problem and it's going to save us a ton

1:39 of money as a you know society if we can do it but we just simply can't. And today we are going to expand on that. We're going to find more uncomputable functions. And so we're going to do this via an idea explored or introduced last time called a reduction which you guys may be familiar with from CS180 where we base the hardness of some new unknown function based on something that we already know about an existing hard

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.