Based on mathworld, The determination of whether a Turing machine will come to a halt given a particular input program. The halting problem is solvable for machines with less than four states.
