!!Con 2018: If you could solve this word tile puzzle, you could... by Kamal Marhubi

305 views · Published 30 May 2018 · 12:56 · Indexed 16 November 2026

Channel: Confreaks · 2018 · Science & Technology

Watch on YouTube

If you could solve this word tile puzzle, you could solve the halting problem! (Too bad you can’t!) by Kamal Marhubi

The idea that there are undecidable problems – ones that simply cannot be solved with computers – is kind of mind-blowing. The most well-known is the halting problem: given a Turing machine (program), will it halt (terminate)? Many other undecidable problems are either very similar to the halting problem, or very abstract. In this talk I’ll show one that is neither! The Post Correspondence Problem is a word tile puzzle that is actually undecidable. I’ll walk through how to prove this, by building a special puzzle that has a solution if and only if a Turing machine would halt. At the end, I hope you’ll share some of my wonder at the theoretical side of computers!

More from this channel