# An example of an easy to understand undecidable problem

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.

• The formula $\forall x, y \quad xy=xy$ is undecidable in the theory describing the usual group theory. Commented Aug 29, 2016 at 18:08

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

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

• Wikipedia's explanation of the proof of undecidability for the halting problem is really bad. Commented Nov 19, 2013 at 3:23
• Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
– user14972
Commented Mar 26, 2019 at 4:31
• I know this is ancient, but the final example here (Post's correspondence problem) is dealt with better in another answer, below, and was only edited in here a full month after that answer was posted. Commented Jun 9, 2020 at 16:55

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.

• there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character Commented Jan 3, 2012 at 1:33
• @miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments <!-- --> to bypass the edit size limit if you need to fix typos in the future) Commented Jan 3, 2012 at 2:25
• The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg. Commented Apr 5, 2019 at 12:20

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

May be you want to check these:

MagicSquare on mathworld.wolfram

• Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be. Commented Nov 10, 2011 at 8:20
• @ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead? Commented Nov 10, 2011 at 10:12
• Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
– Did
Commented Nov 10, 2011 at 10:20
• @DidierPiau: Thank you for your comment and clear instructions. Commented Nov 10, 2011 at 13:06

Maybe consider some Wang Tiles.