If $A$ and $B$ are finite subsets of $\mathbb{R}^n$, then we say that $A$ and $B$ are linearly separable if there exists a hyperplane such that all the points in $A$ are on one side of the hyperplane and all the points in $B$ are on the other side of the hyperplane. This is a useful concept in machine learning.
Now if two sets are linearly separable, then the perceptron algorithm will eventually halt and tell you not only that they are linearly separable but will identify a specific hyperplane that separates $A$ and $B$. But my question is, is there any algorithm that will tell you that two sets are not linearly separable? Or is that an undecidable problem?
Let $A$ and $B$ be two sets. Like @flan said, you could compute the convex hull of either of the both sets, named $C(A)$ and $C(B)$.
The original sets are linear separable iff their convex hulls do not intersect and there is no inclusion relationship. What you now have to do is simply to calculate for every vertex, edge or facet of $C(A)$, namely $x$ and every vertex, edge or facet of $C(B)$, namely $y$, the intersection $x \cap y$.
If any of these intersections is not empty, the convex hulls "collide" and therefore $A$ and $B$ are not linear separable.
You should find the algorithms to calculate the intersections in every computer graphics book.
The last check to do is wether one hull is contained in the other, but this can be easily shown as solvable (hint: to check wether a point is in a convex hull, describe the convex hull (a simplex) as intersection of linear inequalities. Like in Linear programming. These inequalities are simple to check).
If we get that there is no inclusion relationship, we know that the sets are linear separable. Otherwise, they are not.
Props @flan for pointing out the correct solution.
There may be an algorithm with better complexity, but you only asked for decidability. The answer is: Yes, the problem is decidable.