Indecibilidad

Un sistema formal es indecidible si no dispone de un algoritmo o procedimiento de decisión para determinar, en un número finito de pasos, si un enunciado o fórmula de este sistema es un teorema del mismo. La lógica de enunciados es decidible, dado que dispone de un medio mecánico, las tablas de verdad, para poder determinar, para cualquier fórmula dada, si es o no una verdad lógica, una contradicción o una contingencia. La lógica de predicados de primer orden, en cambio, no lo es, según el teorema de Church (1936).