undecidable

Adjective

Meaning

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

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

Synonyms

Antonyms

Related terms

Examples

Because of the two meanings of the word undecidable, the term independent is sometimes used instead of undecidable for the "neither provable nor refutable" sense. Source: Internet

As with many undecidable questions, one can still attempt to give useful approximate solutions. Source: Internet

Conway proved that the problem: : Given g and n, does the sequence of iterates reach 1? is undecidable, by representing the halting problem in this way. Source: Internet

Douglas S. Robertson offers Conway's game of life as an example: citation The underlying rules are simple and complete, but there are formally undecidable questions about the game's behaviors. Source: Internet

For example, Rice's theorem shows that each of the following sets of computable functions is undecidable: * The class of computable functions that return 0 for every input, and its complement. Source: Internet

For instance, first-order logic is undecidable, meaning a sound, complete and terminating decision algorithm is impossible. Source: Internet

Close letter words and terms