undecidable

Adjective

undecidable (not comparable)

1. Incapable of being algorithmically decided in finite time. For example, a set of strings is undecidable if it is impossible to program a computer (even one with infinite memory) to determine whether or not specified strings are included.
   • The first-order procedure SP differs from the proposi-
     tional procedure CP°₁ in an essential feature. Namely, CP°₁
     always terminates while SP may run forever as we have seen with
     the example immediately after (3.7). This is not a specific
     defect of SP. Rather it is known that first-order logic is...1982, Wolfgang Bibel, Automated Theorem Proving, Braunschweig: Friedr. Vieweg & Sohn, →ISBN, page 83
2. (of a WFF) logically independent from the axioms of a given theory; i.e., that it can never be either proved or disproved (i.e., have its negation proved) on the basis of the axioms of the given theory. (Note: this latter definition is independent of any time bounds or computability issues, i.e., more Platonic.)