A logical system or theory is decidable if the set of all well-formed formulas valid in the system is decidable. That is, there exists an algorithm such that for every formula in the system the algorithm is capable of deciding in finitely many steps whether the formula is valid in the system or not. Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is most often said to be the study of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... The word theory has a number of distinct meanings in different fields of knowledge, depending on their methodologies and the context of discussion. ... In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... In logic, the form of an argument is valid precisely if it cannot lead from true premises to a false conclusion. ...

Example: Propositional logic is decidable, because there exists for it an algorithm—truth-table construction—such that for every formula which combines M atomic formulas there is a maximum number N = 2^M of steps such that after completing those N steps the algorithm will always decide whether the formula is valid or not. Here, a "step" of the algorithm has been (arbitrarily) defined as completion of a row of the truth-table. Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ... Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...

First-order logic is decidable if confined to predicates with only one argument (see monadic predicate calculus). If it includes predicates with two or more arguments, then it is not decidable. Famous examples of decidable first-order theories include the theory of real closed fields, and Presburger arithmetic. First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ... In logic, the monadic predicate calculus is the fragment of predicate calculus in which all predicate letters are monadic (that is, they take only one argument), and there are no function letters. ... In mathematics, a real closed field is an ordered field F in which any of the following equivalent conditions are true: Every non-negative element of F has a square root in F, and any polynomial of odd degree with coefficients in F has at least one root in F... Presburger arithmetic is the first-order theory of the natural numbers with addition. ...

Every complete recursively enumerable theory is decidable. On the other hand, every consistent theory which includes some basic arithmetic is undecidable. In mathematical logic, a theory is complete, if it contains either or as a theorem for every sentence in its language. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts...

Decidability should not be confused with completeness. For example, the theory of algebraically closed fields is decidable but incomplete, whereas true arithmetic (the set of all true first-order statements about nonnegative integers in the language with + and ×) is complete but undecidable. Unfortunately, as a terminological ambiguity, the term "undecidable statement" is sometimes used as a synonym for independent statement. In mathematical logic, a theory is complete, if it contains either or as a theorem for every sentence in its language. ... In mathematics, a field F is said to be algebraically closed if every polynomial of degree at least 1, with coefficients in F, has a zero (root) in F (i. ... In mathematical logic, a sentence σ is called independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that σ is false. ...