An algorithm is a deterministic automaton for achieving a goal that, starting from a given initial state, will end in a final state. The quality of the implementation depends on its speed, size and resource consumption.

Resume Summary

What is an algorithm?

There is no generally accepted definition of the word "algorithm."
Simple definition: A set of instructions for solving a problem.

The algorithm is either implemented by a program or simulated. Algorithms often have steps that are iterated (repeated) or require logical decisions or comparisons.

A very simple example of an algorithm is the multiplication of two numbers: on early computers with limited processors, this was achieved by a subroutine, which in a number of cycles based on the first number added the second number. The algorithm translates the method into computer commands.

Algorithms are necessary for computers to process information because a program is actually an algorithm that tells a computer what steps to take and in what order to complete a given task, such as calculating staff salaries or student grades. Thus, an algorithm can be considered as any sequence of operations that can be performed by a Turing-complete system. Among the authors supporting this thesis, Gurevich:

"Informal

Turing's argument for his thesis justifies a stronger thesis: any algorithm can be modeled by a Turing machine."

и Savage:

"An algorithm is a computational process defined by a Turing machine."

Typically, when the algorithm is involved in information processing, data is read from an input source, or device, written to an output, or device. peripheral and/or stored for further processing. A data record is considered as an internal part of the object executing the algorithm. In practice, the state is stored in the data structure.

For all these computational processes, the algorithm must be strictly defined: it must be determined how it behaves in all possible circumstances. Moreover, all conditional steps should be systematically considered in each specific case; the criteria for each should be clear and computable.

Because an algorithm is an exact list of exact steps, the order of calculations will always be critical to how the algorithm works. Instructions must be explicitly defined and described from top to bottom, an idea formally expressed as a control flow. Up to this point, discussion of the definition of the algorithm involved imperative programming. This is the most common concept; it attempts to describe the problem by discrete, "mechanical" means. The concept of assigning a value to a variable is specific to this concept. This leads to the idea of ​ ​ "memory" as a piece of paper.

Functional programming or logic programming offers different concepts of what an algorithm is.

Word algorithm definitions

Blass and Gurevich

Blass and Gurevich describe their work as inspired by Turing machines, Kolmogorov-Uspensky machines (KU machines), Schönhage storage modification machine (SMM), and pointing machines defined by Knut, Gandhi and Markov are also considered as influential predecessors.

Gurewicz offers a clear definition of what an algorithm is (summarized here):

Turing's informal argument for his thesis justifies a stronger thesis: any algorithm can be modeled by a Turing machine. In practice, this may seem ridiculous. Can we generalize machinability so that any algorithm, regardless of the degree of its abstraction, is modeled by a common machine? But suppose such a generalized Turing machine exists. What would her states be? First-order structure... In all cases, a small specific set of instructions will suffice. Processing would be an evolution of the state. It can be non-deterministic, can interact with its environment, be parallel and multi-agent, have dynamic semantics. Two points of support for their work: Turing's theses and Tarski's idea of ​ ​ the structure of the first order.

The above sentence "processing as state evolution" differs markedly from the definition of Knuth and Stone's algorithm as a Turing machine program. Rather, it corresponds to what Turing called a complete configuration, which includes both the current instruction (state) and the tape state. Kleene (1952) shows an example of a tape with 6 characters on it, all other squares are white, and as "Gödelize" the combined status of the table-tape.

Boulos and Jeffrey

Their definition is:

"Explicit instructions for defining the n-th member of the set, for n arbitrarily finite. Such instructions are given quite explicitly, in a form that can be used by a computer." calculate or by a person who is able to transpose very basic operations into characters."

Whip

Knuth (1968, 1973) gave a list of five properties that are widely accepted as prerequisites of the algorithm:

1. Finiteness: "The algorithm must always end after a finite number of steps."
2. Exact definition: "Each step of the algorithm must be precisely defined; actions to be transferred must be strictly and unambiguously defined for each case
.
3. Entrances:... " values ​ ​ given to him before the start of the algorithm. This input is from a specified set of objects.
4. Output:... " Quantities that have a specific relation to the input data.
5. Bandwidth:... " all operations that the algorithm must perform must be sufficiently basic that they can in principle be performed in a finite time by a person using paper and pencil."

Knuth proposes as an example the Euclidean algorithm for determining the greatest common divisor of two integers.

Knuth acknowledges that while his description of what an algorithm is can be intuitively clear, it lacks formal rigor, while it is not exactly clear what "precisely defined" means, or "strictly and uniquely defined," or "sufficiently basic," and so on. He makes efforts in this direction in his first volume, where he defines in detail what he calls "machine language" for his "mythical MIX... the first polyunsaturated computer." in the world." Many of the book's algorithms are written in MIX. It also uses tree diagrams, flowcharts, and state diagrams.

Markov

A. A. Markov (1954) gives the following definition of the algorithm:

"In mathematics, an "algorithm" is generally understood as an exact prescription that determines the processing procedure leading from different initial data to the desired result..."

"The following three characteristics are specific to algorithms and determine their role in mathematics:

a) the accuracy of the recipe, leaving no room for arbitrariness, and its universal comprehensibility, thus, a certain aspect of the algorithm;

b) possibility of starting from the initial data, which can change within the specified limits: commonality of the algorithm;

c) the orientation of the algorithm in finding the desired result, which should ultimately be obtained from its own initial data: the conclusion of the algorithm's property."

His definition, he admits, "doesn't pretend to be mathematically accurate." His 1954 monograph was an attempt to define the algorithm more precisely; the resulting definition - his formal algorithm - he saw as "equivalent to the notion of a recursive function." This definition included four main components: 1. Separate the elementary steps, each of which is performed according to one of the substitution rules given at the beginning.

2. Steps of a local nature.

3. Algorithm schema: formula substitution rules.

4. How to identify imputation for conclusion.

In his Introduction, Markov noted that "all the significance for mathematics" of efforts to more accurately define the "algorithm" may be related to the problem of the structural foundation for mathematics.

Minsk

Minsky (1967) argues that the algorithm is an "efficient procedure" and is synonymous with it.
The term is used by other authors, including Knuth. What Minsky calls an "effective procedure" is defined as follows:

"A set of rules that tells us, moment to moment, exactly how to behave."

However, he acknowledges that this is open to criticism:

"The interpretation of the rules is left to any person or agent."

This leads him to improve to indicate "along with the rules instructions the details of the mechanism that interprets them. To avoid the tedious process of having to do this all the time for each new procedure, he expects to identify a fairly homogeneous family of mechanisms that follow the rules. He puts it this way:

"(1) the language in which the codes of conduct are expressed, and

(2) a single machine that can interpret instructions in language and thus transpose the steps of said process."

However, in the end, he still laments that the subjective side remains. Different people may disagree on whether this or that procedure can be considered effective.

But Minsky does not give up. It immediately releases "Turing Computational Process Analysis." In it, he describes what he calls Turing's thesis:

Any process that could naturally be called an effective procedure can be implemented by a Turing machine.
This is also called Church's thesis.

After analyzing the "Turing Argument," he observes the equivalence of many intuitive formulations of Turing, Church, Kleene, Post and Smullian, which leads to the assumption that there really is an objective or absolute concept.

Stone

Stone (1972) and Knuth were professors at Stanford University at the same time, and we are not surprised to find similarities in their definitions:

"So we define the algorithm

int multiply(int x, int y) 
   int sum = 0 
   while y > 0 
      sum + x 
   let y - 1 
return sum 

int a = 5 
int b = 7 

print a,"x", b, "=", multiply(a, b)

Références

• Martin Davis. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press, 1965.
  Davis fournit un commentaire avant chaque article.
• Yuri Gurevich. Successive abstract state machines capture successive algorithms, ACM Transactions on Computational Logic, Vol 1, No. 1 (July 2000), pages 77-111 .
  Inclut une bibliographie de 33 sources.
• A. A. Markov. Algorithm theory. Imprint Moscow, USSR Academy of Sciences, 1954. Titre original: Teoriya algerifmov.
• Marvin Minsky. Вычисление: Finite and Infinite Machines, First, Prentice-Hall, Englewood Cliffs, NJ. 1967.
• Harold S. Stone. Introduction to Computer Organization and Data Structures, 1972, McGraw-Hill, New York .
  n particulier le premier chapitre intitulé: Algorithms, Turing machines and programs.

Algorithms

Word algorithm definition - Classification - History of algorithms - List of algorithms - Eratosthenes sieve - Fibonacci number