A propriedade relacionada ao Problema da Validade ´e a decidibilidade, ou seja, a classificação do sistema como possuindo, ou não, um método implementável em um computador, de maneira que, para quaisquer enunciados P1, P2, . . . , Pn e C do sistema, quando executamos o método passo-a-passo, podemos responder em uma quantidade finita de tempo e gastando uma quantidade finita de informação, se C é ou não consequência de P1, P2, . . . , Pn.