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 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 mathematics (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.)

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.

    Conservapedia - Recent changes [en] 2009

  • But the "undecidable" stuff needs a lot more care.

    Conservapedia - Recent changes [en] 2009

  • But the "undecidable" stuff needs a lot more care.

    Conservapedia - Recent changes [en] 2009

  • 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.

    In praise of … Tomas Tranströmer | Editorial 2011

  • 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.