En este trabajo, estudiamos tres problemas algorítmicos que involucran árboles de computación: los problemas de optimización, solucionabilidad y satisfacibilidad. El problema de solucionabilidad se preocupa por reconocer árboles de computación que resuelven problemas. El problema de satisfacibilidad se preocupa por reconocer oraciones que son verdaderas en al menos una estructura de un conjunto dado de estructuras. Estudiamos cómo la decidibilidad del problema de optimización depende de la decidibilidad de los problemas de solucionabilidad y satisfacibilidad. También consideramos varios ejemplos con problemas de solucionabilidad y satisfacibilidad tanto decidibles como no decidibles.