Definition of "undecidable" [undecidable]

• 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. (adjective)
• (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.) (adjective)

Wiktionary.org : Text is available under the Creative Commons Attribution-ShareAlike License

• "Whether this difference is only perspectival or whether we deal with an interactive many-worlds "world" even at the global level may remain undecidable, too."
• "We should remark that this problem is non-trivial since deciding whether a finite set of equations provides a basis for Boolean algebra is undecidable, that is, it does not permit an algorithmic representation; also, the problem was attacked by Robbins, Huntington, Tarski and many of his students with no success."
• "But the "undecidable" stuff needs a lot more care."