Читать книгу Information Organization of the Universe and Living Things - Alain Cardon - Страница 9

Mathematicians and computer scientists have been interested in the classes of functions that can be calculated with algorithms, which are automatic calculation processes understood as sequences of instructions defining the values that the variables of the activated functions take. An algorithm is therefore a sequence of instructions that calculates the value of various specific functions, and is defined by its various steps.

The mathematician Alan Turing, in 1936, before the invention of the first computers, posited the existence of an abstract machine capable of calculating all the values of any mathematical function defined on the integers according to an automatic process. Such a machine consists of an infinite tape for storing data and has two parts – one used to read the new data and the other to store them. These data are numbers, which are interpreted by a reading system and written by a writing system and which transmits the read values to the instructions of the machine which uses them to produce the result, which is another sequence of numbers placed in the memorizing part of the tape (see Figure 1.1). There is thus a reading–writing head which makes it possible to specify the actions for processing the instructions. The machine is, at each step of calculation, in a state which is represented by a certain numerically indexed symbol and it is given a precise quantity of these states during its construction. The program of the machine is a set of instructions processing the read values to produce a numerical result. Each instruction has two parts: its trigger to activate and its action to process the value read from the tape. The correct instruction is activated by the trigger and it reads and processes the digital data that is being accessed on the read tape. Its action is to use and rewrite this value read in the same cell of the tape so that it can be used by other machines and then to move the reading head by one cell or not to move it, and then possibly to change its state to specify another one.

An elementary instruction of the Turing machine thus has the form of the following quadruplet (q_i, S_j, S_k, q_s) with:

q_i is the current state of the machine;

S_j is the piece of data which is read on the reading head;

S_k is the numeric character that will replace S_j;

q_s is the new current state of the machine after the replacement.

However, the machine can also have one of the following two forms, with D and G being the actions of simply moving the read head to the right or left without writing anything on the read–write tape:

(q_i, S_j, D, q_s)

(q_i, S_j, G, q_s)

This machine is totally automatic, and it is the most elementary possible with regard to the calculations to be carried out. It is the most important universal machine in the history of computation. All the algorithms use sequences of instructions and are therefore sophisticated compositions of Turing machines, and the instructions can lead to the request after their execution to place themselves on another instruction to be executed by the famous “Go to” and this repeatedly until meeting the instruction “End” of the end of execution of the instructions of the algorithm.

The functions that the Turing machine computes are called recursive primitive functions and they operate on sequences of natural numbers. They are obtained from basic functions, like identity, projection, successor function, using composition, recurrence and minimization, and they are executed in associations. They define all the usual arithmetic functions by machine associations, like power functions, products and sorts, and they are thus the basic model of what can be defined in mathematics to operate on sequences of integers.

Figure 1.1. The Turing machine

All the calculations of the values of numerical functions are thus based on the design of Turing machines. We define a general function on a given problem and its effective calculation amounts to defining the set of Turing machines which will represent it.

However, we can proceed in a much more general way by using the differential equations of mathematics. In this framework, we first define functions and constants specifying the elements in relation in a physical system describing a natural phenomenon and we place these functions in differential equations representing the spatial–temporal relations between the observable elements of the phenomenon. We then seek the solutions of these differential equations giving the values of the functions and thus giving the solution of the problem of the relations and movements by comparing with the results of the physical observation to validate the equations. However, this problem does not always offer a good solution in fundamental physics which uses differential equations and partial differential equations representing the relations between the functions which are the characters of the studied problem, because the solution of these equations, if they are indeed calculable, is not always in agreement with the experimental measurements.

This approach is characterized as ascending, because we start from the observation of the phenomenon and we try to represent it by variables and functions that describe its evolution. It is therefore assumed that there is a space available and that the physical phenomena that occur in this space with structured elements must be precisely described to measure their evolution.