Undecidable Problems: Reducibility (Part 1) | What are Reductions?
A reduction is when we view a problem as another, and by solving the new problem, we solve our initial problem. For example, we may reduce our problem of getting around a new city, to the problem of finding a map of the city; by finding a map, we solve our initial problem of finding our way.
We use reductions in computer science to prove that some problems are undecidable or unsolvable.
Reductions can be a little tricky to understand at first, so this video provides some additional ways to understand reductions and how we can use reductions to show that a problem is undecidable.
If you do reference Michael Sipser's Introduction to the Theory of Computation textbook, then the Truth Problem is actually A_TM (defined in chapter 4.2 on page 174 in the 2nd edition).
____________________
Additional resources:
• Undecidable Problems: ...
- My next video (part 2 of reductions) that show how exactly we can reduce the Halting Problem to the Truth Problem.
• The Halting Problem: T...
- My previous video on the Halting Problem, a well known undecidable problem.
Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
- The main source of my Theory of Computation knowledge (a textbook). Read Chapter 5: Reducibility to learn more about reducibility and how a formal proof would look like.
_____________________
And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.
Пікірлер: 34
I've never seen CS concepts explained in such a soothing way
You stuck a goldmine for content opportunities here. This has to be the most innovative explanation for The theory of computation.
That's it I'm opening a dragon shop
@carlos_3143
Жыл бұрын
Yay, pet dragon!
@adarshmohapatra5058
26 күн бұрын
But to open a dragon shop, you need to first find a dragon
@bencomer2339
3 күн бұрын
@@adarshmohapatra5058Only if you want to make money :)
Awesome to see the concept broken down so simply!
Never comment on videos but really love how this CS concept is so calmly explained in such a fun way!
This is so adorable! I really like the way you explain this!
I love your channel! Thank you so much for putting in the time and effort to make these videos.
Great content, simplified and thus better to learn!
What a fantastic channel!!! GREAT job!! 👏🏼👏🏼👏🏼
The cutest way of learning Computation Theory😇
you made a great explanatory video, good job Lydia :)
I know you put alot of effort on this! thank you and god bless you
Great video! Although I had to sit though logic, so now you do too :p - its not a contradiction to say "Iff there are dragon shops, there are dragons. But there are no dragon shops". That just means the if statement was false. It'd be a contradiction if the if-statement was true (meaning there are dragons) AND there were no dragons.
Thank you for this Great video! I hope you continue to teach one day
You are the best!
great video
Your voice is so ❤️
Great way to calmly explain hard concepts. Never knew CS could be so CUUUTE. Love you and I'll show your channel to all my girlies
great vid, but can;t hear anything despite turning the volume up...
Who said dragons only reside in a dragon shop?
These examples of proofing computers can´t solve any problems, is like trying to proof a computer can do psychotherapy to a patient to talk about his problems, the halting problem follows the same logic, the issue boils down on asking a liar if it is raining or not, he will check the weather and lie to me, telling me opposite of a fact, in logic is impossible to verify if the information given is correct or not, computers do solve the issue to see if halts or loops, just processes the information which was given independently if the information is correct or not, it doesn´t choose or has the ability to know if it has been fooled with wrong input, I can also make a simple C code, in which 1 +1 equals 3.
Voice is low
There are no dragons in my world?
Poor Mary!!!
Dragons don't existtt????
All Mary has to do is look inside the hollow earth tunnels in the American southwest to find dragons. Or at least lizard people. *conspiracy intensifies*
ratio
but I want a dragon :(
way too quiet
@thegeneralgamer4921
2 жыл бұрын
Yeah I had it on full volume and could barely hear. Usually 30/100 is deafening for most videos
you reduce volume in every alternate video 😒