Decidability | Research & Encyclopedia Articles

Decidability

In logic and mathematics, a statement—an assertion within the formal language of a theory--is decidable if it can be shown to be either true or false. In other words, a statement is decidable if either it or its negation can be proved within the theory. For example, the negation of the statement "There exists some whole number that evenly divides the number 43" can be proven within formal arithmetic, which means that the statement is decidable. If a statement or well-formed formula within a theory is undecidable, then the theory is called incomplete.

In the early 1900s, German mathematician David Hilbert brought up the question of whether mathematics itself was complete, that is, whether a formal system could be created that would generate all the true mathematical statements that exist and none others. "Hilbert's programme," as his project was called, would create its formal system on the foundations of the logical developments of George Boole and Gottlob Frege in the 1800s. Boole had developed a purely symbolic system for solving logical problems, and Frege had later extended this system into a predicate calculus (what's often referred to today as first-order logic). Any mathematical domain can be translated into the predicate calculus through an appropriate choice of predicates and variables, so this logical system seemed like a useful tool towards completing Hilbert's programme.

Unfortunately, in his 1931 paper "On Formally Undecidable Propositions Of Principia Mathematica And Related Systems," Kurt Gödel proved that formal arithmetic--the simple addition and multiplication of whole numbers--was incomplete. He did this by translating the language of mathematics into terms from predicate calculus and then creating and proving a statement that said no proof of that very same statement exists because if it did, a contradiction would arise. Gödel had created a statement that could not be proven either true or false, a statement that was not decidable.

But Gödel's findings went well beyond his Undecidability Theorem. He went on to prove that arithmetic alone cannot prove itself consistent. No matter how many axioms one adds to formal arithmetic, it will always contain undecidable statements. This conclusion is known as Gödel's Incompleteness Theorem.

British mathematician Alan Turing expanded on Gödel's work later that decade by demonstrating that for some statements no algorithmic functions exist that can be computed by any logical machine. The machine that Turing envisioned on paper is an abstract representation of a computing device. It consists of no more than a printhead that prints and erases a limited set of symbols on an indefinitely long spool of paper that is divided into squares. The machine could be put into several internal "states," and depending on the state the machine is in, the printhead either prints a character on a blank square, erases a character, or erases a character and prints a new one, after which it moves either left or right one square and changes into a new state.

The behavior of the Turing machine is guided by only three characteristics: the state the machine is in, the character in the square it's examining, and its instructions. A sample instruction might be (a, 1, 0, R, c), which means, "If in state a and the square contains a '1,' erase it and replace it with a '0,' move right, and go into state c." While a Turing machine may sound like a primitive device, every computer that's ever been made is in essence a Turing machine.

While working with its finite set of symbols and states that describe mathematical terms, a Turing machine would run until it found a solution to the problem it was meant to solve, at which point it would stop. But Turing showed that one could create problems for which no solution would ever be found. When confronted with an undecidable problem like this, the machine would run forever. As with Gödel's Undecidability Theorem above, Turing demonstrated that sometimes no algorithmic procedure exists that will enable one to compute whether a statement is either true or false.

Undecidable statements and noncomputable problems are uncommon in practice, but Gödel's and Turing's findings both point out limitations in logic, mathematics and automated computation that practitioners in these fields must be aware of.