Short answers, pulled from the story.
An undecidable problem is a decision problem for which it is proved impossible to construct an algorithm that always gives a correct yes-or-no answer. The halting problem is the most famous example: Alan Turing proved in 1936 that no algorithm can correctly determine whether an arbitrary program will eventually halt for all possible inputs.
The halting problem asks whether a given program, running on a given input, will eventually stop or run forever. Alan Turing proved in 1936 that no general algorithm running on a Turing machine can solve this for all possible program-input pairs. The proof shows that assuming such an algorithm exists leads to a logical contradiction through self-reference.
The halting problem and Gödel's incompleteness theorems are deeply connected: the proofs are structurally similar and a weaker form of Gödel's First Incompleteness Theorem follows directly from the undecidability of the halting problem. Both results reveal a shared mathematical boundary between what computation and formal proof can achieve.
Yuri Matiyasevich, a Russian mathematician, showed in 1970 that Hilbert's Tenth Problem cannot be solved. Hilbert had posed the problem in 1900, asking for an algorithm to find all integer solutions to any Diophantine equation. Matiyasevich proved no such algorithm exists by mapping the problem to a recursively enumerable set and invoking Gödel's Incompleteness Theorem.
"Undecidable" has two distinct meanings. In the sense used by Gödel, a statement is undecidable if it can neither be proved nor refuted within a given formal system. In the sense used in computability theory, a problem is undecidable if no computable function can answer every question it poses correctly. The two are related: a computably undecidable problem implies no consistent formal system can systematically prove its answers.
Yes. In 2019, Ben-David and colleagues constructed a learning model called EMX and showed that the learnability of a certain family of functions within that model is undecidable in standard set theory. This demonstrated that fundamental questions about what a model can learn are not merely computationally hard but provably beyond the reach of any algorithm.