Talking head
!!Con 2018

This presentation, by Kamal Marhubi, is licensed under a Creative Commons Attribution ShareAlike 3.0

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!

Rated: Everyone
Viewed 187 times
Tags: There are no tags for this video.