I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, without mathematics, that is with analogies and intuition, avoiding technicalities.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
"Does this statement follow from these axioms?"
"Does this computer program ever stop?"
"Can this set of domino-like tiles tile the plane?"
"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
There is also a large list on wikipedia.
I think the Post correspondence problem is a very good example of a simple undecideable problem that is also relatively unknown.
Given a finite set of string tuples
the problem is to determine if there is a finite sequence of these tuples , allowing for repetition, such that the concatenation of the first half is equal to the concatenation of second half
The only big issue I have with this problem is that the only undecideability proof I know of falls back on simulating a Turing machine - it would be nice to find a more elementary alternate version.
May be you want to check these:
MagicSquare on mathworld.wolfram
"does this computer program ever stop?"
"does this equation have any solutions?" (of course you mean polynomial equation with integer solutions, but for a general public presentation you can probably get away with just "equation" and "solutions").