Decidability (logic)
In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them.
known for
notableIdea
Wikipage disambiguates
20th century in scienceAbelian groupAdmissible ruleAlasdair UrquhartAlfred TarskiAlgorithmAlgorithmically random sequenceAlloy (specification language)Anatoly MaltsevAndrzej_GrzegorczykAutomated theorem provingAutomatic sequenceBar inductionBernays–Schönfinkel classBoolean algebras canonically definedBoolean ringBurton DrebenBüchi's problemBüchi arithmeticCertificate (complexity)Church–Turing thesisComputability logicComputable analysisConstant problemConstructive set theoryContext-free grammarCoqDecidabilityDecidability (Logic)Decidability (computer science)Decidability of first-order theories of the real numbersDecidable (logic)Decidable sublanguages of set theoryDecision problemDehornoy orderDependence logicDependent MLDescription logicEffective methodEntscheidungsproblem
Link from a Wikipage to another Wikipage
sub discipline
primaryTopic
Decidability (logic)
In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them.
has abstract
Em lógica, o termo decidível s ...... importantes são indecidíveis.
@pt
En , la decidibilitat és una p ...... el cinquè postulat d'Euclides.
@ca
En logique mathématique, le te ...... lle-ci est sous forme logique.
@fr
En metalógica, la decidibilida ...... do de la geometría euclidiana.
@es
In logic, a true/false decisio ...... all cases) can exist for them.
@en
Rozhodnutelnost je matematický ...... ödelovými větami o neúplnosti.
@cs
Rozstrzygalność (decydowalność ...... aby do powstania sprzeczności.
@pl
Алгоритмическая разрешимость — ...... е общей проблемы разрешимости.
@ru
Алгоритмічна розв'язність — вл ...... гальної проблеми розв'язності.
@uk
決定可能（けっていかのう、英: decidable）は、論理 ...... 含まれるか否かを決定する実効的方法があれば、決定可能である。
@ja
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,026,053,919
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
type
comment
Em lógica, o termo decidível s ...... importantes são indecidíveis.
@pt
En , la decidibilitat és una p ...... si la fórmula és vàlida o no.
@ca
En logique mathématique, le te ...... lle-ci est sous forme logique.
@fr
En metalógica, la decidibilida ...... si la fórmula es válida o no.
@es
In logic, a true/false decisio ...... all cases) can exist for them.
@en
Rozhodnutelnost je matematický ...... ödelovými větami o neúplnosti.
@cs
Rozstrzygalność (decydowalność ...... aby do powstania sprzeczności.
@pl
Алгоритмическая разрешимость — ...... е общей проблемы разрешимости.
@ru
Алгоритмічна розв'язність — вл ...... гальної проблеми розв'язності.
@uk
決定可能（けっていかのう、英: decidable）は、論理 ...... 含まれるか否かを決定する実効的方法があれば、決定可能である。
@ja
label
Decidability (logic)
@en
Decidibilidad
@es
Decidibilidade
@pt
Decidibilitat
@ca
Décidabilité
@fr
Rozhodnutelnost
@cs
Rozstrzygalność
@pl
Алгоритмическая разрешимость
@ru
Алгоритмічна розв'язність
@uk
決定可能性
@ja