undecidable

undecidable
a) 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.
b) (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.)
See Also: noncomputable

Wikipedia foundation.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Undecidable — has more than one meaning:;In mathematical logic: * A decision problem is called (recursively) undecidable if no algorithm can decide it, such as for Turing s halting problem; see also under Decidable and Undecidable problem. * Undecidable is… …   Wikipedia

  • UNDECIDABLE — Martin Davis, The Undecidable, Raven Press, 1965 (informationswissenschaftl. Veoeffentlichung) …   Acronyms

  • UNDECIDABLE — Martin Davis, The Undecidable, Raven Press, 1965 (informationswissenschaftl. Veröffentlichung) …   Acronyms von A bis Z

  • Undecidable problem — In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct an algorithm that leads to a yes or no answer the problem is not decidable.A decision problem is any …   Wikipedia

  • undecidable — adj. * * * …   Universalium

  • undecidable — adjective not able to be firmly established or refuted. Derivatives undecidability noun …   English new terms dictionary

  • undecidable — un·decidable …   English syllables

  • undecidable — /ʌndəˈsaɪdəbəl/ (say unduh suyduhbuhl) adjective not decidable. –undecidability /ʌndəsaɪdəˈbɪləti/ (say unduhsuyduh biluhtee), noun …  

  • undecidable — |ən+ adjective : not capable of being decided …   Useful english dictionary

  • On Formally Undecidable Propositions of Principia Mathematica and Related Systems — This article describes the publication details of a famous paper in mathematical logic. For information about the theorems proved in this paper, see Gödel s incompleteness theorems. Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”