Definitions

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.

Etymologies

Sorry, no etymologies found.

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.

  • 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

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

    Conservapedia - Recent changes [en]

  • 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

  • It transpires that the theory of arithmetic (technically, Peano arithmetic) is both incomplete and undecidable.

    Archive 2009-06-01

  • However, undecidable statements which are free from self-reference have been found in various branches of mathematics.

    Archive 2009-06-01

  • 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

  • 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

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

    Archive 2009-06-01

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

    Theories of Everything and Godel's theorem

Wordnik is becoming a not-for-profit! Read our announcement here.

Comments

Log in or sign up to get involved in the conversation. It's quick and easy.