lowed correctly, will lead to a recognizable end result. Simply put, a recipe is an exam-
ple of an algorithm. For example, if there are two different recipes for making apple
pie—one calling for cutting fresh apples for the filling, the other calling for apples
from a can—the end results will be the same: an apple pie.
In mathematics, most algorithms include a finite sequence of steps that repeat, or
require decisions using logic and comparisons until the final result is found (often
called a computation). The best example is the long-division algorithm, in which the
remainders of partial divisions are carried to the next digit or digits. For example, in
the division of 1,347 by 8, a remainder of 5 in the division of 13 by 8 is placed in front
of the 4, and 8 is then divided into “54,” and so on. More advanced use of algorithms
are found in a type of logic called metamathematics (see below).
How is a decision problemconnected to algorithms?
A decision problem is also known as an Entscheidungsproblem,which stems from the
German. Decision problems bring up the question of whether an algorithm represents a
specific mathematical assertion or not, as well as whether it has or does not have a proof.
What is metamathematics?
Metamathematics is the study of mathematical reasoning in a general and abstract
way, usually by trying to understand how theorems are derived from axioms. Thus, it
is often called proof theory (for more information about axioms, see below). It does
not study the objects of a particular mathematical theory, but examines the mathe-
matical theories themselves with respect to their logical structure. Metamathematics
is also used in logic to study the combination and application of mathematical sym-
bols; this is often referred to as metalogic.
What is Gödel’s Incompleteness Theorem?
Austrian-American mathematician and logician Kurt Gödel (1906–1978) is best
known for his studies in mathematical logic—in particular, his “incompleteness theo-
rem,” presented in 1931. This theorem shows that an infinite number of propositions
that can’t be derived from axioms of a system may be proved by metamathematical
means external to mathematics. In other words, mathematics abounds with questions
that have a “yes or no” nature; the incompleteness theory suggests that such ques-
tions will always exist. (For more about Gödel, see “History of Mathematics.”)
What are some more recent philosophiesof mathematical logic?
Mathematical knowledge and logic in the late 20th and early 21st centuries has been
greatly impacted by the development of predicate calculus and the digital computer. Out
of these ideas—not to mention centuries of mathematics and logic groundwork—come
three of the latest philosophical doctrines of mathematical thought. 113