Decision problems for which it is unknown whether they are decidable In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
 A: An integer linear recurrence sequence is a sequence $x_0, x_1, x_2, \ldots$ of integers that obeys a linear recurrence relation
$$x_n = a_1 x_{n-1} + a_2 x_{n-2} + \cdots + a_d x_{n-d}$$
for some integer $d\ge 1$, some integer coefficients $a_1, \ldots, a_d$, and all $n\ge d$.  The following problem is sometimes known as "Skolem's problem":

Given $d$, $a_1, \ldots, a_d$, $x_0, \ldots x_{d-1}$, does there exist $n$ such that $x_n=0$ ?

It is unknown whether the above problem is undecidable.  For more information, see Terry Tao's blog post on the subject.
A: Inspired by a previous (now deleted) post:
We do not know if every even natural number (at least four) is a sum of two primes [Goldbach, 1742]. However, there is a simple algorithm that decides if a given even number (at least four) is a sum of two primes.
Similarly but differently, we do not know if every even natural number is a difference of two primes [Maillet, 1905].  Here there is no (known) algorithm that decides if a given even number is a difference of two primes.
These are the examples given in Gödel, Escher, Bach to teach the reader about the difference between bounded and unbounded search.

After a few searches, ending here, I found that there are more difficult, and earlier, versions of Maillet's question.  Kronecker [1901] asks if every even natural number is the difference of two primes in infinitely many ways.  Polignac [1849] asks if every even natural number is the difference of infinitely many pairs of consecutive primes.  These two conjectures have their related decision problems.  However, now the unbounded search is much worse...
A: In Conway's Game of Life, the problem of deciding whether a given pattern with finitely many live cells is a Garden of Eden (i.e. whether it lacks a predecessor).
The main obstacle is that there could be a pattern which has finitely many live cells and a predecessor, but such that all of its predecessors have infinitely many live cells. If we knew there were no such patterns then the problem would be decidable.
Added 2019 December 3: Having learnt about the problem from this post, Ville Salo and Ilkka Törmä have produced a paper ("Gardens of Eden in the Game of Life") showing that this problem is decidable. Interestingly, they don't proceed via the method I suggested here. It remains an open problem to determine if there is a non-Garden-of-Eden pattern with finitely many live cells all of whose predecessors have infinitely many live cells.
Added 2022 January 18: In fact it is false that a finite pattern without finite predecessors must necessarily be a Garden of Eden. This result is also due to Salo and Törmä.
A: It remains open whether the won-position problem of infinite chess is decidable, the problem of determining whether a given finite position in infinite chess is winning for white or not. See Richard Stanley's question at https://mathoverflow.net/q/27967. Meanwhile, the mate-in-$n$ problem of infinite chess is decidable, and so the open part of the problem necessarily concerns positions with infinite game value.
Also open is the optimal-play problem: given a won position, is a given move optimal?
A: In response to this CompSciTheory (cstheory) question,
A simple problem whose decidability is not known
,
I posted that:

It is unknown whether or not
  it is decidable to determine if a given shape can tile the plane,

referring to an earlier cstheory question.
This is even open for polyomino tiles.

          


          

(Image from Wikipedia.)


A: One problem about decidability that continues to attract a lot of attention is extensions of Hilbert's 10th problem to other rings of number-theoretic interest, especially the rationals $\mathbb{Q}$. See for instance this nice survey paper of Poonen.
A: The word problem for a finitely presented group $G = \langle A \mid R \rangle $ and the associated canonical homomorphism $\pi : F_A \to G$, asks: given an element $w \in F_A$, do we have $\pi(w) = 1$? There exists finitely presented groups in which the word problem is undecidable, a result independently due to Novikov and Boone.
However, W. Magnus showed that for one-relator groups, i.e. groups $G = \langle A \mid w= 1 \rangle$ with a single defining relation, the word problem is always decidable (though the time-complexity of this solution remains unknown in general as far as I am aware).
The following natural problem, however, remains open:

Is the word problem always decidable for two-relator groups $G = \langle A \mid w_1 = 1, w_2 = 1 \rangle$?

This appears in the Kourovka Notebook as Problem 9.29.
There are also concrete examples of groups for which we do not know whether their word problem is decidable or not. For example, we know very little about how to solve the word problem in most Artin groups. The following is an open problem which appears in the previous link:

Let $G = \langle a, b, c, d \mid aba=bab, ad = da, bdb = dbd, aca = cac, bcb = cbc, cdc = dcd\rangle$.
Is the word problem for $G$ decidable?

It is somewhat surprising that this problem is open -- if one considers the semigroup presentation with the same generators and the same defining relations, then the word problem (appropriately phrased as the problem of comparing two words) is easily solvable!
A: Perhaps the biggest open problem in symbolic dynamics is the equivalence problem for subshifts of finite type.
Given a finite alphabet $\mathcal{A}$ and a finite set $\mathcal{F}$ of finite words over $\mathcal{A}$ (the forbidden words), the corresponding subshift of finite type consists of


*

*The space $S\subseteq \mathcal{A}^\mathbb{Z}$ of all bi-infinite words over $\mathcal{A}$ that do not have any of the forbidden words as subwords, and

*The shift map $\sigma \colon S\to S$ that shifts each symbol to the left one spot.
Two subshifts $(S,\sigma)$ and $(S',\sigma')$ of finite type are equivalent if they are conjugate as dynamical systems, i.e. if there exists a homeomorphism $h\colon S\to S'$ such that $h\circ \sigma = \sigma'\circ h$.

Is there an algorithm to determine whether two subshifts of finite type $(S,\sigma)$ and $(S',\sigma')$ are equivalent?

See M. Boyle, Open problems in symbolic dynamics. Contemporary mathematics 469 (2008): 69-118.
A solution to this problem was famously published in the Annals of Mathematics by R. F. Williams in a 1973 paper.  An error was found in his proof, so the correctness of his main classification algorithm became the "Williams conjecture".  This conjecture was disproven by K. H. Kim and F. W. Roush in 1990's in a series of two papers, and at present we have essentially no idea whether equivalence is decidable.
A: $k$-Piece Dissection is not known to be decidable.  Given two polygons and an integer $k$, is there a dissection of the first polygon into k pieces that can be reassembled into the second one?
