Algorithm - 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, an algorithm is a computational process defined by a Turing machine".

Typically, when an algorithm is associated with processing information, data is read from an input source, written to an output device, and/or stored for further processing. Stored data is 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 such computational process, the algorithm must be rigorously defined: specified in the way it applies in all possible circumstances that could arise. That is, 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 will always be critical 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, this discussion of the formalization of an algorithm has assumed the premises of imperative programming. This is the most common conception, and it attempts to describe a task in discrete, "mechanical" means. Unique to this conception of formalized algorithms is the assignment operation, setting the value of a variable. It derives from the intuition of "memory" as a scratchpad. There is an example below of such an assignment.

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

Read more about this topic:  Algorithm

Other articles related to "formalization, formalizations":

Closed World Assumption - Formalization in Logic
... The first formalization of the closed world assumption in formal logic consists in adding to the knowledge base the negation of the literals that are not currently entailed by it ... In other words, this formalization of the closed world assumption sometimes turns a consistent knowledge base into an inconsistent one ... Alternative formalizations not suffering from this problem have been proposed ...
Law Of Value - Theorizing The Value of Labour-products - Formalization
... Underlying this debate are difficult conceptual questions about how the causal relationships in the economy between price relativities and time worked should be understood ... Marx's analysis of value was "dialectical" in the sense that he thought value phenomena could only be understood dynamically, holistically and relationally, but he did not spell out all the conceptual, quantitative and logical implications of his position with great exactitude ...
Method Engineering Process - Formalization and Application Techniques
... method language begins to approach maturity, mathematical formalization techniques are employed so the emerging language has clear syntax and semantics ... The method formalization process often helps uncover ambiguities, identify awkward language structures, and streamline the language ...

Formalization may refer to

  • formal system in formal logic
  • a process enhancing bureaucracy in sociology
Institute For Liberty And Democracy - Activities in Peru - Property Rights Campaign
... confirmed that 80 to 90 percent of the population supported "formalization" of the poor's real estate assets ... a new project from the ILD to extend formalization further. 803 in March 1996, creating the Commission for the Formalization of Informal Property (COFOPRI) as well as the start-up programs and the strategy for that ...