Потому что перечислимые множества это совершенно не то же самое, что разрешимые (принадлежность которым можно проверить за конечное число операций). И первый пример тут — множество кодов программ, которые когда-нибудь останавливаются, перечислимо (ибо можно запустить симулятор + перебор кодов + параллелизацию), но не разрешимо (ибо теорема Тьюринга и парадокс лжеца).