(of a formal theory) having the property that it is possible by a mechanistic procedure to determine whether or not any well-formed formula is a theorem
decidable in American English
(dɪˈsaidəbəl)
adjective
1.
capable of being decided
2. Logic(of an axiom, proposition, etc.)
having the property that its consistency or inconsistency with the axioms of a given logical system is determinable
Derived forms
decidability
noun
Word origin
[1585–95; decide + -able]This word is first recorded in the period 1585–95. Other words that entered Englishat around the same time include: aberration, corridor, filament, sine, titular-able is a suffix meaning “capable of, susceptible of, fit for, tending to, given to,”associated in meaning with the word able, occurring in loanwords from Latin (laudable); used in English as a highly productive suffix to form adjectives by addition tostems of any origin (teachable; photographable)
Examples of 'decidable' in a sentence
decidable
However, when restricting to memoryless strategies the model-checking problem becomes decidable.
Steen Vester 2013, 'Alternating-time temporal logic with finite-memory strategies', Electronic Proceedings in Theoretical Computer Sciencehttp://arxiv.org/pdf/1307.4476v1. Retrieved from DOAJ CC BY 4.0 (https://creativecommons.org/licenses/by-sa/4.0/legalcode)
In general, these logics are undecidable, but we use our translations to identify decidable fragments.
Carlos Areces, Raul Fervari, Guillaume Hoffmann, Mauricio Martel 2016, 'Relation-Changing Logics as Fragments of Hybrid Logics', Electronic Proceedings in Theoretical Computer Sciencehttp://arxiv.org/pdf/1609.04086v1. Retrieved from DOAJ CC BY 4.0 (https://creativecommons.org/licenses/by-sa/4.0/legalcode)
We show that such games are undecidable in general, and become decidable for visiblypushdown automata specifications.
Ilaria De Crescenzo, Salvatore La Torre, Yaron Velner 2014, 'Visibly Pushdown Modular Games', Electronic Proceedings in Theoretical Computer Sciencehttp://arxiv.org/pdf/1408.5969v1. Retrieved from DOAJ CC BY 4.0 (https://creativecommons.org/licenses/by-sa/4.0/legalcode)
This relationship implies that the equivalence checking problem and the minimization problem for these transducers are also decidable.
Vladimir A. Zakharov, Shynar R. Zhailauova 2017, 'On the Minimization Problem for Sequential Programs', Modelirovanie i Analiz Informacionnyh Sistemhttps://www.mais-journal.ru/jour/article/view/532. Retrieved from DOAJ CC BY 4.0 (https://creativecommons.org/licenses/by-sa/4.0/legalcode)
We then devise a decidable system with annotated terms, justified in terms of the unannotated system.
Vilhelm Sjöberg, Aaron Stump 2011, 'Equality, Quasi-Implicit Products, and Large Eliminations', Electronic Proceedings in Theoretical Computer Sciencehttp://arxiv.org/pdf/1101.4430v1. Retrieved from DOAJ CC BY 4.0 (https://creativecommons.org/licenses/by-sa/4.0/legalcode)