!!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
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
-
35:52
Code Design and the Science of Pleasure
-
48:58
Ruby Software Continuously Delivered and Exhaustively Explained by Brian Guthrie, Srushti Ambekallu
-
40:58
Jruby Polyglot Heaven by Thomas E Enebo and Charles Oliver Nutter
-
42:17
Be a Minecraft modman with Purugin by Thomas E. Enebo
-
36:46
Your tests are lying to you by Chris Parsons
-
23:46
KidsRuby: Think Of The Children! by Ron Evans
-
52:05
Resources, For Real This Time (with Webmachine) by Sean Cribbs
-
38:28
Just Say No To :nodoc: and Document Your Code! by Loren Segal