Save this video free

CSCD 420 Nov 12 2026

Chris Cain · 51:17 · Watch on YouTube

Part of Eastern Washington University CSCD 420. See all 32 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

Chris Cain introduces the hierarchy of formal languages, distinguishing recursively enumerable languages, whose Turing machines accept members but may loop on nonmembers, from recursive languages, whose machines halt with a yes-or-no answer on every input. He develops enumeration procedures using membership tests and dovetailing, applies Cantor diagonalization to show that some languages cannot be enumerated, and constructs a universal Turing machine that simulates encoded machine-input pairs.

Key takeaways

Chapters

0:00 Course Announcements and the Shift to Language Hierarchies
3:10 Why Recursively Enumerable Languages Matter
5:48 Recursively Enumerable Languages Permit Infinite Loops
7:35 Recursive Languages Always Decide Membership
12:00 Enumerating Recursive Languages with a Generator and Membership Test
18:18 Dovetailing Recognizers to Enumerate Recursively Enumerable Languages
27:43 Cantor Diagonalization and Languages Beyond Enumeration
36:16 Complements Reveal the Difference Between Recursive and Enumerable
40:13 Defining the Universal Language of Machine-Input Pairs
43:51 A Four-Tape Universal Turing Machine Simulates Encoded Programs

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

Transcript excerpt

0:02 Time for us to get started. How's everybody doing? Excellent. We're feeling more vocal than usual today. All right, we'll start with our usual announcements. We have a homework assignment due tonight. I'll be getting the next one out to you reasonably quickly so that you can get started on that over the weekend. It's also getting time to start thinking about the next exam. I will be getting the exam that you took last week back to you tomorrow. So it will be a plan that we're we're going over that tomorrow. We'll have the opportunity to see how you did and go over all the questions on the exam.

0:50 I will not be recording that as usual, so I recommend being here in person or attending remotely at the same time. Other than that, I don't think there's anything else to to think about. Anyone have any questions on the schedule? >> Yeah, when it comes to seeing the test scores each day, I mentioned that or should we just wait until tomorrow too? >> We'll probably have to wait till tomorrow. I have not yet received the stickied version of them for review yet. So I actually don't have the ability to offer that. Sorry. But I will have them by tomorrow. Other questions? Okay. Last time we were talking about

1:41 the last bit of Turing machine models of addendums that we could make to Turing machines, and we also talked about interesting limitations we could make to Turing machines, and we ended up finding that the most interesting restriction we could make was a linear bounded automata, one that we restrict the length of the to the size of the input and what kinds of languages can we interestingly accept with that. And we looked at one example

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, Chris Cain.

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.