Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 34 down vote accepted

"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?"
(The halting-problem, from which identifying buffer overflows 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.

share|improve this answer
4  
@downvoter: care to explain? This is a correct answer. –  BlueRaja - Danny Pflughoeft Nov 10 '11 at 6:42
    
+1;and indeed I would like to know about the down-vote too. –  Quixotic Nov 10 '11 at 7:12
    
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad. –  Daniel Nov 19 '13 at 3:23

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

share|improve this answer
    
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be. –  ShreevatsaR Nov 10 '11 at 8:20
    
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead? –  Emmad Kareem Nov 10 '11 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 Nov 10 '11 at 10:20
    
@DidierPiau: Thank you for your comment and clear instructions. –  Emmad Kareem Nov 10 '11 at 13:06

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

(a , bba) 1
(ab,  aa) 2
(bba, bb) 3

It is asked if there is a finite sequence of these tuples (allowing for repetition) so that the concatenation of the first half is equal to the concatenation of second half

(bba, bb) 3
(ab,  aa) 2
(bba, bb) 3
(a,  bba) 1
------------ 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 ...

share|improve this answer
    
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character –  miracle173 Jan 3 '12 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) –  hugomg Jan 3 '12 at 2:25

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

share|improve this answer
    
Ya that's the idea I was going to go with. –  comp Nov 10 '11 at 5:02
1  
@downvoter: care to explain your action? (three answers to this question received unexplained downvotes). –  Alon Amit Nov 11 '11 at 17:18

Maybe consider some Wang Tiles.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.