Formalization
Algorithms are essential to the way computers process data. Many computer programs contain algorithms that detail the specific instructions a computer should perform—in a specific order—to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards. Thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Authors who assert this thesis include Minsky (1967), Savage (1987) and Gurevich (2000):

Minsky: “But we will also maintain, with Turing … that any procedure which could “naturally” be called effective, can, in fact, be realized by a (simple) machine. Although this may seem extreme, the arguments … in its favor are hard to refute”.
Gurevich: “… Turing’s informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine … according to Savage 1987, an algorithm is a computational process defined by a Turing machine”.

Turing machines can define computational processes that do not terminate. The informal definitions of algorithms generally require that the algorithm always terminates. This requirement renders the task of deciding whether a formal procedure is an algorithm impossible in the general case—due to a major theorem of computability theory known as the halting problem.

Typically, when an algorithm is associated with processing information, data can be read from an input source, written to an output device and stored for further processing. Stored data are regarded as part of the internal state of the entity performing the algorithm. In practice, the state is stored in one or more data structures.

For some of these computational processes, the algorithm must be rigorously defined: specified in the way it applies in all possible circumstances that could arise. This means that any conditional steps must be systematically dealt with, case-by-case; the criteria for each case must be clear (and computable).

Because an algorithm is a precise list of precise steps, the order of computation is always crucial to the functioning of the algorithm. Instructions are usually assumed to be listed explicitly, and are described as starting “from the top” and going “down to the bottom”—an idea that is described more formally by flow of control.

So far, the discussion on the formalization of an algorithm has assumed the premises of imperative programming. This is the most common conception—one which attempts to describe a task in discrete, “mechanical” means. Unique to this conception of formalized algorithms is the assignment operation, which sets the value of a variable. It derives from the intuition of “memory” as a scratchpad. An example of such an assignment can be found below.

For some alternate conceptions of what constitutes an algorithm, see functional programming and logic programming.

Expressing algorithms
Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, drakon-charts, programming languages or control tables (processed by interpreters). Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode, flowcharts, drakon-charts and control tables are structured ways to express algorithms that avoid many of the ambiguities common in the statements based on natural language. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are also often used as a way to define or document algorithms.

There is a wide variety of representations possible and one can express a given Turing machine program as a sequence of machine tables (see finite-state machine, state transition table and control table for more), as flowcharts and drakon-charts (see state diagram for more), or as a form of rudimentary machine code or assembly code called “sets of quadruples” (see Turing machine for more).

Representations of algorithms can be classed into three accepted levels of Turing machine description, as follows:

1 High-level description
“…prose to describe an algorithm, ignoring the implementation details. At this level, we do not need to mention how the machine manages its tape or head.”

2 Implementation description
“…prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level, we do not give details of states or transition function.”

3 Formal description
Most detailed, “lowest level”, gives the Turing machine’s “state table”.
For an example of the simple algorithm “Add m+n” described in all three levels.

To Chapter 40