Monday, September 9, 2013

A Simple Problem Whose Decidability Is Not Known

An interesting CS Theory Stack Exchange question (via @CompSciFact):

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering on discussing the concept of decidability. I want to give an example of a problem which we do not currently know to be decidable or undecidable. There are many such problems, but none seem to stand out as nice examples so far.

What is a simple-to-describe problem whose decidability is open?

Comments RSS · Twitter

Leave a Comment