Self-Replicating Machines and the Limits of Computation | #SoME4
Audience: high-schoolundergraduate
Tags: programmingcomputer-sciencecodinghalting-problemself-referenceundecidable-problem
With the recent drastic improvements in AI systems, computers seem to be far more capable and intelligent than ever before. However, there are certain problems even the most powerful of computers will never be able to solve. In this video, we explore how the ability of computers to self-replicate and reference their own source code leads to proofs that certain interesting computational tasks are actually impossible! This video is designed for students who are familiar with the basics of coding, but are still coming to terms with what is and isn't possible.
Analytics
Comments
I really enjoyed the puzzle explanations in the video. The video was novel and I learned a lot from it. The animations were super clean and this was very well done over all. I recommend going deeper into the real-world implications of the result from the proof. Additionally, I suggest adding more content and reflection to the conclusion of the video.
Would’ve been better with more examples
Just a very solidly done, compelling explanation of self-reference proofs in the theory of computation, very nicely done. I’m leaving some room at the top of the scale for anything that really blows me away, which this couldn’t quite do for me personally since I was already fairly familiar with the subject, but I’ve got no big negative notes on that at all. Dropped a subscription, might check out your previous videos another time.
ok, I’m biased because I love coding puzzles like this, but I find this video to be a really interesting and simple explanation of what appears to be very complex at first glance.
Very interesting topic - I have no complaints about the presentation. The explanations were clear and the visuals were good and i liked the fact that there were many examples. As for the exercises at the end, I think putting them there was a good idea but i wish there were solutions for them! (maybe in the description?).
Very well planned video! Interesting examples that were relevant for further understanding of the concepts!
It’s a good explanation video with some neat animation. The video got me hooked till the 5 minute mark then it starts to lose.
The work needed is more in why I should keep paying attention, some voice modulation and keep me track on where the video is going. Suddenly, I feel lost in bunch of coding and it’s thinking while the larger point is lost, which could be conveyed much faster or more interestingly.
Keep up.
Question: What’s one thing you found especially impressive or well-done
Answer: I found that the pacing/flow of this whole video was very well done! It started with an introduction into a seemingly simple question of self replication, answering that question, and transitioning into the halting problem. The pacing was slow enough to give time to think whilst being fast enough to not be boring. I was never lost or confused and didn’t have to look up anything else in order to understand the material at hand.
Motivation
By starting the video with a very simple problem of is a self replicating machine possible, you were able to hook viewer into the topic at hand. Very nice!
Clarity
You were able to introduce the concepts of computer science for people who are unfamiliar with coding using a creating pseudo-programming language(sushi). You were also able to teach people with programming experience (like me) with an interesting and simple problem of self-replication, and show the solution in programming languages like python and c. I think this video is a great introduction into the halting problem, whilst also offering new information, and better understanding to those who might have already been familiar with the topic.
Novelty
Whilst the Halting problem is one of the most famous problem in computer science. You were able to bring a new perspective I’ve never seen before. By introduction self referential programs you brought new light into something that I think most programmer have never thought about.
Memorability
I think a lot of the proof were very simple and elegant especially the halting problem. With the fundamentals of self reference being introduced at the start. I think many viewers will find the halting problem is a “aha” moment!
Overall, I don’t really have anything to critique. So this comment might be useful, but I really enjoyed your video! :)
Great choice of topic, great and concise explanation. The only thing I could ask would’ve been for you to explain it a bit slower. I had to pause the video again and again to understand all of the arguments. But the presentation was great. The clarity that I got from the video, about a topic that I hadn’t previously studied was great. I’m already recommending the video to my friends in computer science.
Amazing video. It explains several important ideas in complexity theory in an understandable way. The animations are phenomenal and strongly aid in the exposition.
Minor remarks:
- The explanation about what makes something “more difficult to design” is good but non-rigorous, so claiming a kind of paradox with self-reproducing factories is kind of premature. Indeed if A is reducible to B, we typically write this as B >= A not B > A.
- I think you could emphasize more strongly that algorithms do exist that can correctly identify many halting and non-halting programs (including lots that come up in practice), but the halting problem asks for a single algorithm that’s always right about if a program halts.
- The remark about needing to deal with quotation marks when writing quines strikes me as a bit of a red herring. Indeed quotation marks make things tricky for most programming languages people use today (python, java, c, etc), but the definition of quine applies to any encoding of Turing machines.
- I wonder if uncomputability of Kolmogorov complexity would have been a slightly simpler version of the minimal program result presented here
The presentation is clear, albeit at times too succinct. Students might sometimes appreciate keeping somewhere in reference the core concepts that had been introduced prior. Given the focus on illustrating through visual proofs and the streamlined presentation, I believe some snippets that invite the viewer to ponder the subject a short amount of time would go a long way towards making all the effort even more impactful. The visuals and duo are well chosen. Audio levels and microphones might benefit from being a bit more aligned in the future. A fun presentation, thank you!