Definitions
from The Century Dictionary.
- Incapable of being decided, settled, or solved.
from Wiktionary, Creative Commons Attribution/Share-Alike License.
- adjective mathematics, computing theory Incapable of being
algorithmically decided infinite time. For example, a set ofstrings is undecidable if it is impossible to program acomputer (even one with infinitememory ) to determine whether or not specified strings are included. - adjective mathematics (of a
WFF ) logically independent from theaxioms 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.)
Etymologies
Sorry, no etymologies found.
Support
Help support Wordnik (and make this page ad-free) by adopting the word undecidable.
Examples
-
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.
Chaosmic Orders: Nonclassical Physics, Allegory, and the Epistemology of Blake's Minute Particulars. 2001
-
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.
Automated Reasoning Portoraro, Frederic 2005
-
But the "undecidable" stuff needs a lot more care.
-
But the "undecidable" stuff needs a lot more care.
-
But the "undecidable" stuff needs a lot more care.
-
However, undecidable statements which are free from self-reference have been found in various branches of mathematics.
Archive 2009-06-01 Gordon McCabe 2009
-
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.
Archive 2009-06-01 Gordon McCabe 2009
-
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.
Archive 2009-06-01 Gordon McCabe 2009
-
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.
Archive 2009-06-01 Gordon McCabe 2009
Comments
Log in or sign up to get involved in the conversation. It's quick and easy.