Pourquoi la validité logique du premier ordre (sans arithmétique) est-elle seulement énumérable et non récursive?

Question

La «complexité de calcul» de Papadimitriou indique que la validité, le problème de décider si une formule logique de premier ordre (sans arithmétique) est valide, est récursivement énumérable. Cela découle des théorèmes d'exhaustivité et de solidité, qui assimilent la validité et le théorie, ces derniers étant le problème de trouver une preuve pour une formule, qui s'était auparavant démontrée que c'était récursivement énumérable.

Cependant, je ne vois pas pourquoi la validité n'est pas aussi récursive, car étant donné une formule $ phi $, l'une pourrait exécuter deux machines de Turing pour le théorié, l'une sur $ phi $ et l'autre sur $ neg phi $, simultanément . Étant donné qu'au moins l'un d'entre eux est valide, il est toujours possible de décider si $ phi $ est valide ou non valide. Qu'est-ce que je rate?

Remarque: cette question fait référence à la logique de premier ordre sans pour autant Arithmétique, donc le théorème d'incomplétude de Gödel n'a pas de roulement ici.