I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that 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 decision problem whose decidability is open?
The Matrix Mortality Problem for 2x2 matrices. I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?
(The 3x3 case is known to be undecidable. The 1x1 case, of course, is decidable.)
UPDATE: The problem I mentioned here is now known to be undecidable! http://arxiv.org/abs/1605.05274 Moreover, the paper was inspired by reading this very answer. :)
Programmers in your math-major audience may be surprised to learn that the question "is this type implicitly convertible to that type?" is not known to be decidable in any of Java 5, C# 4 and Scala 2.
For more details, see Andrew Kennedy and Benjamin Pierce's paper "On Decidability of Nominal Subtyping with Variance". The paper gives some examples of additional restrictions to the type systems of these languages, under which nominal subtyping becomes known to be decidable or known to be undecidable.
Interestingly, the paper was written well before generic covariance and contravariance were added to C#, but the authors correctly anticipated the direction the language was heading. (This is unsurprising; the authors designed the underlying support for variance in the CLR that I took advantage of when adding variance to C#! They did the heavy lifting.)
Hilbert's tenth problem over rationals: "Does this polynomial equation have a rational solution?"
The problem of given a linear recurrence along with its initial values, does it take the value 0?
Two reference:
http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/
http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf
A simple problem whose decidability is unknown is the following (I think it is still open):
Infinite chess:
Input: A finite list of chess pieces and their starting positions on a $Z \times Z$ chessboard;
Question: Can White force mate?
If we add the constraint that White must mate in $n$ moves ($n$ is part of the input), then it becomes decidable: see Dan Brumleve, Joel David Hamkins, and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable.
Another simple problem is the behaviour of Langton's ant on finite initial configuration.
Langton's ant behaviour with finite support:
Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:
Input: a finite configuration (black/white) of the plane and the ant position;
Question: Does the ant always end building a recurrent infinite "highway"?
For infinite support the problem is undecidable, see: A. Gajardo, A. Moreira and E. Goles, Complexity of Langton’s ant
Collatz Problem is simple-to-describe problem whose decidability is open. It involves a simple recurrence of elementary arithmetic operations.
$f(n)=\mathsf{\{}$ $n/2$ for even integer, $3n+1$ for odd integer
The problem is deciding whether iterating this function always return to 1 for a given positive integer $n_0$.
Interestingly, a generalization of the Collatz problem was shown to be undecidable.
References:
1- UNDECIDABLE PROBLEMS: A SAMPLER, BJORN POONEN
2- Weisstein, Eric W. "Collatz Problem." From MathWorld--A Wolfram Web Resource.
3- The 3X+1 Problem: An Overview, Jeffrey C. Lagarias
It is unknown whether or not it is decidable to determine if a given shape can tile the plane, even for polyomino tiles.
The decidability of conjunctive query containment has been open for over twenty years. Resolving this would be a breakthrough in database theory.
Query containment takes as input two queries $Q_1$ and $Q_2$ and asks whether $Q_1$ applied to any database $I$ yields at least as many answers as $Q_2$ when applied to the same database $I$.
In conjunctive queries one uses AND to link together existentially quantified predicates. In SQL terms, conjunctive queries are the SELECT-FROM-WHERE queries using "=" and "AND" but no subqueries or aggregation. This is perhaps the most common kind of database query, and includes most search engine queries.
What makes query containment potentially undecidable is the quantification over infinitely many possible databases $I$. Algorithms that do exist tend to rely on turning this infinite quantification into a syntactic question, whether there is a homomorphism of some kind between $Q_1$ and $Q_2$.
For slightly more powerful (i.e. "advanced") queries that allow OR or $\ne$, query containment is known to be undecidable.
To compare queries by counting how many answers they generate, one uses the semiring $(N,+,\times)$ of natural numbers with addition and multiplication. Query containment can also be generalized to other ordered semirings. For all positive semirings, conjunctive query containment is NP-hard. However, for most semirings other than $(N,+,\times)$ that people care about, conjunctive query containment is decidable. Unfortunately, the counting case falls into the zone of semirings where decidability of conjunctive query containment is still open.
For pointers to the extensive literature and a rigorous treatment, see a ToDS paper (in press) by some people.
One could turn this into a compelling question for a non-technical audience by demonstrating Googlefight, then asking how one can tell which query gives more answers than the other, without first peeking at the data. If $Q$ and $R$ are conjunctive queries, then $Q$ always gives at least as many answers as $Q \text{ AND } R$, because the latter is somehow syntactically "larger" (there is a homomorphism from $Q$ to it), but things get rather tricky from there on.
Post's Correspondence problem with a fixed number of tiles of between 3 and 6.
While it is not really simple to describe, it does have a very "playful" description, and I find it suitable for intuition-level talks.
The Generalized star-height problem : "how many nesting of Kleene stars do I need to represent this regular language, with a regular expression with complementation allowed ?"
We don't even know if the algorithm that always returns 1 (except 0 for star-free languages, which is a decidable case) is correct.
A problem from Automata Theory.
Input: A DFA $D$ over a binary input alphabet.
Question: Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary? In other words, is $L(D) \cap Primes$ non-empty?
Comments: I originally heard this problem from a stackexchange answer by Jeffrey Shallit. If you know of any references to it, please let me know. Thank you!
Related Posts:
(1) Are there any open problems left about DFAs?
Related Work: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf
"Minimal Elements for the Prime Numbers" by C. Bright, R. Devillers, and J. Shallit
Iterated maps on the interval (description from here):
(very related to the problem proposed by Magnus Find)
Let $F$ be a piecewise-linear map on the unit interval and $x$ a point in this interval. We consider the sequence of iterates starting from $x$: $x$, $F(x)$, $F(F(x))$, and so on. Given $F$ and $x$, does this sequence reach a fixed point of $F$?
Decidability is also unknown for the reachability variant: given $F$ and $x$, and $y$, does the sequence starting from $x$ reach $y$ in a finite number of iterations?
It is open even when $F$ has only two linear pieces.
Remark: for this problem to make sense, $F$ and $x$ (and $y$) must have a finite description. We assume here that $x$ is rational, and that the slopes and breakpoints of $F$ are also rational.
A reference: Asarin 2011.
there seems to be a fairly natural way/angle to study this question that is utilized in at least 3 papers as follows.
let $TM(k,l)$ be the set of Turing Machine with $k$ states and $l$ symbols. for low/small $k,l$ the machines are provably decidable, for larger $k,l$ past some threshhold they are provably undecidable. however in the intermediate region, they are not consistently known to be either decidable or undecidable (and the full table is presumably unknowable based on the same undecidability phenomena of the halting problem).
the results can be displayed on a grid as in some of the following refs. also in the intermediate region it is actually known that some (unresolved) machines are capable of simulating the Collatz conjecture for some inputs.
therefore there is clearly a "transition-point" like phenomena operating here but not within a computable region but in an unusual sense of between computable and uncomputable.
cellular automata, very simple computing devices, have various open questions about undecidability. some of the standard Wolfram CAs are conjectured to be universal (although a simple list of those conjectured undecidable does not seem to be available). in particular CA Rule 54 is conjectured by Wolfram to be Turing-complete. there are only $2^8$ basic CAs which most are now resolved as not Turing complete, but at least one was relatively recently found to be Turing complete, rule 110, in a remarkable proof by Cook, using the CA to emulate a Turing-complete tag system.
also as an example of a "near miss", or "open question relatively recently resolved as TM complete", the Wolfram 2,3 machine was proved universal in 2007 for a $25K prize. the contest was announced in May 2007 and the contest announced the winner Smith in October 2007.
there is a fairly natural way to map most open problems onto questions of (un)decidability. most open problems generally are not known to be provable or unprovable.
on the web there is some informal confusion about the undecidability of the P vs NP problem, which is not strictly a decision problem, therefore to talk about its undecidability is not technically correct. but on the other hand there does seem to be a close/natural link between undecidability and provability as follows.
for example consider
the language $L$ of binary strings where a string/integer $x$ is in the language iff there exists a $O(n^x)$ DTime TM that solves an NP complete problem
is this language decidable? that is an question about a language with its decidability open that is basically closely tied (even, virtually identical) to the P vs NP problem and its inherent (un?)provability.
as for P vs NP as "simple to describe", it only requires concepts of TMs, Big O runtime notation, nondeterminism which are a fairly simple (some of the most basic concepts of TCS) and taught at the undergraduate level or which a gifted high school student could understand.
in fact NP vs P/Poly is also open, and can be mapped onto an open question about decidability in the same way, and this can be stated as a fairly simple problem about the growth of minimal (monotone?) circuits to recognize NP complete problems (eg cliques).
