Turing Machines + Decidability in 3 Hours (TM, Variants, Church-Turing, Decidability)

Here we do a livestream covering everything to do with Turing Machines and Decidability. We cover Turing Machines (and their formal definition), what a "high-level" problem description is, several variants of Turing Machines (nondeterministic, multitape, etc.), the importance and truth of the Church-Turing thesis, encodings of machines, and decidability problems involving DFAs and CFGs.

Timestamps:
0:00 - Intro
7:43 - Start of topics
8:18 - Review/Motivation for a new model
12:13 - Definition of a TM
27:26 - Example of a TM
37:47 - What is a configuration, a computation and few more terms.
45:18 - Decidable language
47:18 - TM Variants
1:06:10 - More TM Variants (Multi-tape TM, Nondeterministic TM)
1:26:20 - Computation tree
1:34:25 - Can TMs do arithmetic?
1:41:15 - Church-Turing Thesis
1:44:09 - Problems for TMs ("High-level" algorithm/Encodings)
1:58:49 - Acceptance problems involving DFA, NFA, Regex, etc.
2:13:42 - "Emptiness" Problem for DFAs (E_DFA)
2:19:15 - "Equivalence" Problem for DFAs (EQ_DFA)
2:28:46 - "Acceptance" Problem (for CFGs)
2:39:14 - "Emptiness" Problem for CFGs
2:48:50 - End

#easytheory #gate #theory

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:

Merch:

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[mutaiib]

Timestamps:
0:00 - Intro
7:43 - Start of topics
8:18 - Review/Motivation for a new model
12:13 - Definition of a TM
27:26 - Example of a TM
37:47 - What is a configuration, a computation and few more terms.
45:18 - Decidable language
47:18 - TM Variants (includes Professors "Stay-Put" machine)
1:00:24 - Taking A Short Break. . .
1:06:10 - More TM Variants (Multi-tape TM, Non deterministic TM)
1:26:20 - Computation tree
1:34:25 - Can TMs do arithmetic?
1:41:15 - Church-Turing Thesis
1:44:09 - Problems for TMs ("High-level" algorithm/Encodings)
1:52:24 - Taking A Short Break. . .
1:58:49 - Decidable problems involving DFA, NFA, REGEX. . .
2:13:42 - "Emptiness" Problem
2:19:15 - "Equivalence" Problem
2:28:46 - "Acceptance" Problem (for context-free grammars)
2:39:14 - "Emptiness" Problem for CFG
2:48:50 - End

[garykim]

Quality is easily 10/10. Thank you for making such great education accessible. There's great education on YouTube, but there's also quite a bit of low quality educational content.

[timothygorden]

Thanks prof LITERALLY saving my semester

[ingridflatland]

you are gonna save my exam, thank you sir!

[dmusic]

People outside CS major watch games/makeup/miscellaneous livestream.
CS major students watch theory-proof livestream.
Lol

[FourAwsomeGamerz]

For the TM shown at 30:47 is the the function that it computes: 0^n -> {x^(n-1) : n is even}

[hudson]

did you do a full video on undecidabiilty or just a bunch of short ones. I saw several shorter videos but was wondering if there was a single comprehensive video that i am missing.

[mysterious]

thank you buddy, can I just say you look like duncan robinson :)

[Megan-glpi]

If Turing Machine variants are equivalent in power to regular Turing Machines, why would you create or use a Turing Machine variant?

[pranayreddy]

This is super helpful! Is there a way to donate in cryptocurrency?

[muhammadshaheer]

Is it necessary that the tape is one way infinite? can't it be two way infinite?

[ridovercascade]

Thank youuuu so helpful, may Allah bless you with Islaam