An example of an easy to understand undecidable problem

Question

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.

Answer 1

"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
(See also word problem)

"Does this statement follow from these axioms?"
(Hilbert's Entscheidungsproblem)

"Does this computer program ever stop?"
"Does this computer program have any security vulnerabilities?"
"Does this computer program do <any non-trivial statement>?"
(The halting-problem, from which all semantic properties can be reduced)

"Can this set of domino-like tiles tile the plane?"
(See Tiling Problem)

"Does this Diophantine equation have an integer solution?"
(See Hilbert's Tenth Problem)

"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
(See Post correspondence problem)

---

There is also a large list on wikipedia.

Answer 2

"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").

Answer 3

May be you want to check these:

Alan_Turing_and_Undecidable_Problems_in_Mathematics on fora.tv

what-are-the-most-attractive-turing-undecidable-problems-in-mathematics on mathoverflow

MagicSquare on mathworld.wolfram

Answer 4

Maybe consider some Wang Tiles.

Answer 5

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, each with an index $i$, a left string $l(i)$ and a right string $r(i)$, the problem is to determine if there is a finite sequence of index values $i(1),i(2),\dots,i(n)$, allowing for repetition, such that the concatenation of the left strings $l(i(1)),\dots,l(i(n))$ is equal to the concatenation of the corresponding right strings $r(i(1)),\dots,r(i(n))$. For example, with three tuples with $(l(i), r(i)), i$ as follows:

(a , baa) X
(ab,  aa) Y
(bba, bb) Z

we may use the index sequence $Z, Y, Z, X$:

(bba, bb) Z
(ab,  aa) Y
(bba, bb) Z
(a,  baa) X
------------ gives
(bbaabbbaa, bbaabbbaa)

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.