Skip to main content
Glite Dictionary
decidability

decidability

8.8
A question about whether a problem can be solved by a clear step by step method
  • noun
  • /dɪˈsaɪdəˌbɪlɪti/
  • Specialized
translation icon : decidibilidad
  • Mathematicians are often concerned with the decidability of statements within formal systems.

Examples

  • In computer science, decidability refers to whether a problem can be definitively solved using a specific method.

  • The former is either true or false, and its decidability is precisely what distinguishes it from representation.

    Academic text (1991)

  • The decidability can only be negative, not positive.

    Academic text (1995)

  • Lewis would admit certain contradictions as long as a certain degree of decidability is maintained.

    Academic text (1995)

  • The decidability of optimal pipelining for a machine with finite resources is an open problem.

    Academic text (1994)

  • There was an analogy here between P and decidability and NP and recognizability.

  • Nor did Chen address issues of language ambiguity, correctness, decidability, acceptance by formal automata, and various other formal requirements of computer languages.

    Academic text (1992)

  • The idea of decidability helps determine if a given question can be answered with a clear yes or no.

Synonyms

solvability
vsdecidability
1 5.5

How possible it is to find an answer to a problem

stresses a definite method to get a yes or no answer, not general solving
computability
vsdecidability
  • Specialized
7.0

How easy it is for a computer or algorithm to solve a problem

focuses on having a definite method to give an answer, not only algorithmic solution

How Decidable

decidability
  • Specialized
8.8
undecidability
  • Specialized
9.9

Surface Forms

decidability singular
decidabilities plural

Morphology

decidability = decidable (transparent) = decide + able + ity

A regular nominalization of the adjective 'decidable' with '-ity', straightforward for learners.

Etymology

Decidability comes from decide, which itself comes from the Latin parts de- 'off' and caedere 'to cut'. Think of decide as 'cutting off' other choices, so decidability means a problem can be clearly cut into a yes or no by a method.