from Wiktionary, Creative Commons Attribution/Share-Alike License
- adj. 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.
- adj. (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.)
from The Century Dictionary and Cyclopedia
- Incapable of being decided, settled, or solved.
Sorry, no etymologies found.
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.
What matters is that the winner deserves it, not the undecidable question of whether the most deserving wins.
It transpires that the theory of arithmetic (technically, Peano arithmetic) is both incomplete and undecidable.
However, undecidable statements which are free from self-reference have been found in various branches of mathematics.
Crucially, however, whilst the theory of a model, Th (M), may be undecidable, it is guaranteed to be complete, and it is the models of a theory which purport to represent physical reality.
Moreover, whilst Peano arithmetic is axiomatizable, there is a particular model of Peano arithmetic, whose theory is typically referred to as Number theory, which Godel demonstrated to be undecidable and non-axiomatizable.
However, even if a final Theory of Everything is incomplete and undecidable, the physical universe will be a model M of that theory, and every sentence in the language of the theory will either belong or not belong to Th (M).
I have found that its assumed use of the square root of minus one is logically independent from the theory's axioms: a subset being the Field Axioms, under which the square root of minus one is a well known and proven undecidable sentence.
Wordnik is becoming a not-for-profit! Read our announcement here.