undecidable

Beyond formal proof

Undecidable describes a problem or proposition that cannot be resolved by any systematic method.

In mathematics and logic, an undecidable statement is one that can neither be proved nor disproved within a given formal system: Gödel showed that any sufficiently powerful system contains undecidable propositions.

In computer science, an undecidable problem has no algorithm guaranteed to produce a correct answer for all inputs.

computational

halting

Marked by hesitation

computabilityAlgorithmic solvability of problems
algorithmFinite problem-solving procedure
recursionProcess invoking itself

Turing · recursive · unsolvable · intractable · Church · enumerable · computable · word problem · Rice · oracle

logical

incompleteness

State of lacking parts

theoremDemonstrated logical conclusion
proofDemonstration of truth
axiomSelf-evident starting principle

paradox · formalism · proposition · sentence · statement · self-reference · consistency · decidability · provability · unprovable

indeterminate

unresolved

Lacking final determination

unsettledNot yet resolved
openNot closed
pendingAwaiting resolution or decision

inconclusive · undetermined · uncertain · indefinite · open-ended · unsolved · unascertained · unestablished · tentative · ambiguous

undecidable

halting

incompleteness

unresolved

undecidable

Opposites

Categories

Family