My favorite "natural" undecidable function is the the Post correspondence problem (https://en.wikipedia.org/wiki/Post_correspondence_problem https://en.wikipedi

My favorite "natural" undecidable function is the the Post correspondence problem (https://en.wikipedia.org/wiki/Post_correspondence_problem https://en.wikipedia.org/wiki/Post_correspondence_problem). In short, imagine I give you a set of dominoes that have strings on the top and the bottom. E.g.: D = { banan/b , 0/an, a/a } (Where 0 is the empty string.) A solution is a sequence of dominoes selected from D with replacement such that the string made up of the tops and the bottoms are the same. In the case of D, the sequence: [banan/b , 0/an, 0/an, a/a] is a solution. Solvable(X) = 1 if there exists a non-trivial solution for X and = 0 if not. So Solvable(D) = 1. Solvable(X) is undecidable. Like a lot of these kinds of problems, the proof is gross, but the basic intuition is that I can encode the compute history of a Turing machine in a set of dominoes so that there is a solution iff the machine halts.