If you could solve this word tile puzzle, you could solve the halting problem! (Too bad you can’t!)
summary
Claims the Post Correspondence Problem is undecidable by giving an explicit reduction from the halting problem: a routine turns any Turing machine into a set of word tiles so that a matching sequence exists if and only if the machine halts. Builds concrete tiles that simulate tape cells, state and head movement, including extra tiles for left moves; the construction generates tens of tiles and succeeds in making the puzzle mirror halting versus looping.
AI-written summary · about
chapters (4)
related talks
21mHow hard can it be! Practical uses of complexity theory
45mThe Conscious Turing Machine (CTM), a formally defined Theoretical model of Consciousness
25mInfinite Worlds from Finite Tile Sets: A "Quantum" Approach to Generative Art
19mNew York Times' Connections: A Case Study on NLP in Word Games
10mSATisfying answers to difficult questions!
01h 10mWinning the War on Error: Solving Halting Problem, Curing Cancer
34mSolving Problems Declaratively
01h 01mUnderstanding Transformers through the Lens of Logic and Automata