6. Algorithms and Turing Machines 6.1. Concept of algorithm

In almost all spheres of life, a person is confronted with recipes for solving problems, prescriptions, instructions, etc. They uniquely determine the order in which actions are taken to obtain the desired result. A prescription satisfying some additional requirements is called an algorithm. For a long time, an intuitive idea of ​​an algorithm as a formal prescription has been formed in mathematics, which defines a set of operations and the order of their execution for solving all problems of any type. The formal definition of the algorithm can be given as follows:

An algorithm is a finite prescription defined in a language (method, recipe) that defines a discrete sequence of executable elementary operations to solve a problem. The process of performing a prescription consists of separate steps, each of which performs one successive operation.

Everyone meets with algorithms from school. The rules by which arithmetic operations are performed are the simplest examples of algorithms. The term “algorithm” itself comes from the name of the medieval Uzbek mathematician Al-Khorezmi, who was still in the 9th century. formulated such rules.

A traditional example is the well-known Euclidean algorithm for finding the greatest common divisor of two given positive integers a and b.

The Euclidean algorithm consists of the following system of sequential instructions: 1) review a and b and go on to the next; 2) compare the observed numbers (a = b, or a <b, or a> b) and go on to the next; 3) if the surveyed numbers are equal, then each of them gives the desired result, if not, go to the next; 4) if the first surveyed number is less than the second, rearrange them and go to the next one; 5) subtract the second number from the first and review two numbers - the deductible and the remainder; proceed to instruction 2.

As can be seen, after the fifth directive one should return to the second one each time until the third directive is fulfilled. Although it is not known in advance how many such cyclic transitions will be required, it is clear that for any two numbers the goal will be achieved in a finite number of steps.

Nowadays, the concept of an algorithm has been thoroughly studied and refined, mainly in connection with the development of cybernetics. From the point of view of modern practice, the algorithm is a program, and the criterion of the algorithmic process is the ability to program it. It is because of this reality of the algorithm, and also because the engineer’s approach to mathematical methods has always been constructive, the concept of algorithm in technology has become extremely popular in a short time (perhaps even more than in mathematics itself).

However, in everyday practice, the word "algorithm" is used too widely, often losing its exact meaning. As a result, the algorithm is often issued any instructions, divided into steps. A clear idea of ​​what an algorithm is is important, of course, not only for proper word usage. It is also necessary when developing specific algorithms, especially when referring to their subsequent programming.

Before proceeding to the study of the basic concepts of the theory of algorithms, we discuss on an informal level some of the basic principles by which algorithms are built, and find out what exactly the concept of an algorithm needs to be refined.