Undecidable Languages - Easy Theory

Watch and track your favorite playlist.

Curated by: Easy Theory (35 videos)

Currently Playing: Mapping Reducibility + Reductions, what are they?

Here we introduce mapping reductions and show that if A mapping reduces to B and B is decidable, then A is also decidable. Easy Theory Website: https://www.easytheory.org GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio Patreon: https://www.patreon.com/EasyTheoryYT Fourthwall: https://easy-theory-llc-shop.fourthwall.com Problem Solving channel: ⁠ @easytheoryprobsolve

Tracks in this Playlist

Acceptance for Turing Machines is Undecidable, but Recognizable
Decidable iff Recognizable and co-Recognizable Proof
Emptiness for Turing Machines is Undecidable
Regularity in Turing Machines is Undecidable
Equivalence for Turing Machines is Undecidable
Emptiness for Linear Bounded Automata is Undecidable
Universality for Context-Free Grammars is Undecidable
Equivalence for Context-Free Grammars is Undecidable and co-Recognizable
Post Correspondence Problem (PCP) is Undecidable Proof
The "Simple" Post Correspondence Problem is Decidable, Open Problems
Mapping Reducibility + Reductions, what are they?
Equivalence for Turing Machines is neither Recognizable nor co-Recognizable
Detection of Ambiguous CFGs is Undecidable
Post Correspondence Problem over Binary Alphabets is Undecidable
Which of these mapping reductions is true?
Mapping Reductions are not Always Possible
Useless Turing Machines are Undecidable
Live Solve of all GATE 2021 Computer Science (CSE) Theory Questions
Is this the hardest exam ever? Solutions included!
Stuck Ships are Undecidable!
Busy Beaver Numbers are Undecidable
Minimal Context-Free Grammars are Undecidable
Private video
Undecidable Languages NOT Closed Under Concatenation
Why There's (Likely) No Pumping Lemma for Context-Sensitive Languages
How accurate is Veritasium about the Collatz 3x+1 Problem?
Rice's Theorem Proof using the Recursion Theorem?! - Easy Theory
Undecidable Language Example: Moving Left Three Times in a Row
How accurate is Tom Scott's "Are There Problems That Computers Can't Solve?" video?
It's Impossible to Deal with So Much Space
Decidable Languages NOT Closed Under Homomorphism
10 Reasons Why Computer Science Theory is Important
Private video
Rice's Theorem (Undecidability): 5 Proofs and Examples
Rice's Theorem Example: Emptiness for Turing Machines