CS 181 Lecture 14 -- Fall 2026, UCLA
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
- A many-one reduction from an uncomputable problem A to B proves B uncomputable only when the input transformation is itself computable.
- HALT reduces to HALT-ON-ZERO by hard-coding a machine M and input x into a program N that ignores its input, simulates M(x), and returns if that simulation halts.
- NOT-EMPTY is uncomputable because a program that ignores its input, simulates M(0), and returns 1 exactly when the simulation ends makes NOT-EMPTY decide HALT-ON-ZERO.
- EXACTLY-ONE is uncomputable by restricting that simulation to one selected input, such as 227, so the constructed program has exactly one successful input if and only if M halts on 0.
- Rice's theorem says every nontrivial property determined only by program input-output behavior is uncomputable, which rules out general algorithms for program equivalence and many forms of software verification.
- Testing finitely many cases cannot prove general program equivalence because there are infinitely many possible inputs and a program may fail to halt.
Chapters
- Eli Jaffe reviews universal Turing machines and the earlier uncomputability results for the toddler function and HALT.
- The lecture's goals are to establish more uncomputable functions using reductions and introduce semantic properties of programs.
- Exam 2 is scheduled for Monday from 6:00 to 7:50 p.m., is closed-note, and covers lectures 9 through 14.
- The material includes regular expressions, the pumping lemma, Myhill-Nerode, Turing machines, and uncomputability; prior exams and solutions are on ESL.
- Homework 4 is due Saturday, November 21, at 9:59 p.m.; lecture is still scheduled for Wednesday, November 25.
- The proposed strategy tries to solve the uncomputable toddler function by using HALT as a subroutine.
- Merely adding a check for whether a machine halts on itself does not repair the earlier algorithm's deeper self-reference problem.
- Evaluating the proposed solver on its own description exposes contradictory output requirements.
- Assume HALT is computable and construct CANT-SOLVE-ME, which loops if its input machine halts on itself and otherwise returns.
- Run CANT-SOLVE-ME on its own description: if it halts, its definition makes it loop; if it does not halt, its definition makes it return.
- Both cases contradict the assumption, so HALT cannot be computed; this is the traditional diagonalization proof.
- The established starting points for further proofs are the uncomputability of the toddler function and HALT.
- Jaffe introduces reductions as a way to transfer uncomputability from a known hard problem to a new problem.
- A reduction maps each input to problem A into an input for problem B, then uses B's answer to obtain A's answer.
- The factoring-to-multiplication analogy illustrates transforming one problem instance into another.
- Unlike many CS180 examples, the inputs here can be treated as encoded bit strings.
- A reduction has to specify its input transformation and explain how the target problem's output answers the original question.
- For uncomputability proofs, efficiency is not required, but the transformation R must be computable.
- Without that condition, an impossible computation could be hidden inside R rather than arising from problem B.
- A many-one reduction makes one call to problem B and directly uses its result for problem A.
- A Turing reduction can make multiple calls to B and post-process their outputs.
- The course focuses on many-one reductions, then introduces HALT-ON-ZERO as a seemingly weaker variant of HALT.
- HALT takes a machine M and input x, and asks whether M halts on x.
- HALT-ON-ZERO takes a machine and asks whether it halts on the single fixed input 0.
- The reduction must construct a new program whose behavior on 0 represents whether the original M halts on x.
- Construct N so it ignores its own input, simulates M on the fixed input x, and returns 1 if that simulation finishes.
- N halts on 0 exactly when M halts on x, so a HALT-ON-ZERO oracle would decide arbitrary HALT instances.
- Hard-coding the descriptions of M and x into N is the core input transformation.
- If M does not halt on x, N never reaches its return instruction, so N does not halt on 0.
- HALT-ON-ZERO is treated as a hypothetical oracle that decides the program's behavior by its description, not by waiting for execution to finish.
- The reduction works because the oracle's answer about N on 0 matches HALT's answer about M on x.
- Jaffe checks both cases: when M halts on x, N reaches return 1; when M does not halt, N loops.
- Constructing N from the descriptions of M and x is computable because it only requires writing a program that invokes evaluation on those fixed values.
- Since HALT reduces to HALT-ON-ZERO and HALT is uncomputable, HALT-ON-ZERO must also be uncomputable.
- The input to HALT-ON-ZERO is N's source-code description; the 0 is the input supplied to N.
- N accepts an input but deliberately ignores it, using its hard-coded M and x instead.
- The contradiction argument is: if HALT-ON-ZERO were computable, the reduction would make HALT computable, contradicting HALT's uncomputability.
- NOT-EMPTY(M) is 1 if there exists an input x for which M(x) = 1, and 0 otherwise.
- A sample program that returns 1 only when its input is 0 is NOT-EMPTY because at least one such input exists.
- HALT-ON-ZERO is chosen as the source problem for proving NOT-EMPTY uncomputable.
- Given M, construct N that ignores its input, evaluates M on 0, and returns 1 if that evaluation finishes.
- If M halts on 0, N returns 1 for every input; if M loops on 0, N never returns 1 for any input.
- The NOT-EMPTY oracle's answer therefore decides HALT-ON-ZERO, and the construction of N is computable.
- EXACTLY-ONE(M) is 1 when precisely one input makes M output 1.
- A program that returns 1 only for input 0 satisfies the property; one that returns 1 for inputs 0 and 1 does not.
- The proof reduces the already established uncomputable HALT-ON-ZERO problem to EXACTLY-ONE.
- The NOT-EMPTY construction makes N return 1 on every input when M halts on 0, so it cannot directly establish EXACTLY-ONE.
- The revised N checks whether its input z equals one chosen constant, such as 227; only then does it evaluate M on 0 and return 1.
- If M halts on 0, exactly one input produces 1; if M does not halt, no input produces 1.
- This computable reduction proves EXACTLY-ONE uncomputable.
- Program equivalence asks whether two programs M and N have the same output behavior for every input x.
- Testing examples, as in programming challenge test suites, can provide evidence but cannot establish equivalence for all possible inputs.
- General equivalence checking matters for software security and hardware verification, yet the property is uncomputable.
- A property is semantic when its value depends only on a program's input-output behavior, not on how its code is written.
- Equivalent programs must either both satisfy a semantic property or both fail it.
- Rice's theorem states that every nontrivial semantic property of programs is uncomputable; properties that are always true or always false are the trivial exceptions.
- HALT-ON-ZERO, NOT-EMPTY, EXACTLY-ONE, HALT, and the toddler function are presented as semantic examples.
- The example property asks whether an arbitrary program has the same input-output behavior as a program computing 2 to the n.
- Different implementations can compute 2 to the n, but an algorithm cannot decide equivalence for every arbitrary program.
- Checking infinitely many inputs or inspecting code structure cannot provide a general decision procedure for such a nontrivial semantic property.
- Hilbert's tenth problem asks whether an integer equation has an integer solution; no algorithm decides the answer for every equation.
- Uncomputability also appears in fields such as physics and chemistry, beyond software verification.
- The course's final three lectures turn to context-free grammars as a model intended to balance computational power with analyzability.
- Jaffe distinguishes proving a particular implementation correct from deciding whether every arbitrary program has a semantic property.
- Testing can build evidence, but a program may continue running, connecting practical verification limits to the halting problem.
- For exam preparation, he recommends knowing the definitions of functions such as HALT, HALT-ON-ZERO, NOT-EMPTY, and EXACTLY-ONE, with HALT-ON-ZERO especially useful for reductions.
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.