Fibonacci's measurement algorithms

At least we have came up to the main unexpected result of the algorithmic measurement theory namely to Fibonacci's measurement algorithms.

Let's return now to the mathematical measurement model based on the "Indicator Elements" and try to introduce the above-considered "Asymmetry Principle of Measurement" in this model.

The following "restriction" as to the moving of the IE along the line segment AB follows from the "Asymmetry Principle of Measurement". Let IE be applied to the point C (Fig. 1) at the first step of the n-step measurement algorithm.

The first step of Fibonacci's optimal algorithm
Figure 1. The first step of Fibonacci's optimal algorithm.

Thereafter there arise two situations (a) and (b) shown in Fig. 1. It is clear that for the situation in Fig. 1-a we can apply IE to some point of the line segment CB at the next step. However for the situation in Fig.1-b we don't have the right to apply the IE to some point of the line segment AC, because the balance should return to the initial position during p units of the discrete time. Thus, the restriction of S following from the "Asymmetry Principle of Measurement" consists of the fact that for the situation in Fig. 1-b it is forbidden to apply the IE to the points of the line segments AC within p steps of the algorithm.

And again we wouldn't like to tire our readers by the keenness of the mathematical reasoning and would like to give the final result. It was proved that for the given p (p = 0, 1, 2, 3, ...) the "effectiveness" function Fp(n) is expressed as the following:

(1)

Let's consider some special cases of formula (1). Let p = 0. For this case formula (1) is reduced to the following:

F0(n) = 2 F0(n - 1);(2)
F0(0) = 1.(3)

It is clear that the recurrent formula (2) with the initial condition (3) "generates" the binary sequence:

1, 2, 4, 8, 16, ... , F0(n) = 2n-1.

The measurement algorithm corresponding to this case is reduced to the classical "binary" algorithm.

Let p = ¥. For the above-considered problem it means that the IE "leaves the field' when it is found to the right of the point X. For this case the formula (1) takes the form Fp(n) = n + 1, what corresponds to the classical "counting" algorithm.

Let's consider the case р = 1. For this case the recurrent formula (1) takes the following form:

F1(n) = F1(n - 1) + F1(n - 2) для n > 2;(4)
F1(1) = 2, F1(2) = 3.(5)

If we calculate now the "effectiveness" function F1(n) according to (4), (5) then we get the following numerical series: 2, 3, 5, 8, 13, 21, 34, ..., which is nothing as Fibonacci numbers! That is why the above-considered measurement algorithms are called Fibonacci's measurement algorithms!

In Table 1 it is given the values of the "effectiveness" function Fp(n) of the optimal Fibonacci algorithms for different values of p.

Table 1.

n123456789
F0(n)248163264128256512
F1(n)23581321345589
F2(n)2346913192841
F3(n)2345710141926
..............................
F¥(n)2345678910

And now let's go to the system of standard weights for Fibonacci's measurement algorithms. It was proved that for this case the "optimal" system of standard weights Wp(n) is given with the following formula:

Wp(n) = Wp(n - 1) + Wp(n - p - 1) для n > p + 1;(6)
Wp(1) = Wp(2) = ... = Wp(p + 1) = 1.(7)

Table 2 gives different variants of the "optimal" systems of standard weights corresponding to the different values of p.

Table 2.

n123456789
W0(n)1248163264128256
W1(n)112358132134
W2(n)1112346913
W3(n)111123457
..............................
W¥(n)111111111

The analysis of the expressions (6), (7) and Table 2 shows that the numbers Wp(n) coincide with the generalized Fibonacci numbers or the p-Fibonacci numbers revealed by us at the Pascal Triangle investigation, in particular with the classical Fibonacci numbers for the case p = 1.

Let's consider the example of the optimal Fibonacci measurement algorithm given with the expression (1). Let p = 1 and n = 5. Let's consider the 5-step Fibonacci algorithm (Fig. 2) corresponding to this case.

The optimal Fibonacci algorithm
Figure 2. The optimal Fibonacci algorithm.

It follows from Table 1 that the above-considered 5-step Fibonacci algorithm divides the initial line segment [0,13] into 13 equal parts. To realize the algorithm we need to use the 5 standard weights, which are in Table 2 namely {1, 1, 2, 3, 5}.

Let's consider the first 3 steps of the given algorithm.

The first step is applying the IE to the point 5 of the line segment [0, 13] (Fig. 2). One can see that the first step is the subdivision of the line segment [0, 13] in the Fibonacci ratio: 13 = 5 + 8. There emerge two situations (a) and (b) after the first step.

The second step.

  1. For this situation we use the next standard weight 3 and subdivide the line segment [5, 13] by the IE in the Fibonacci ratio: 8 = 3 + 5. There are also two situations (c) and (d) after the second step.
  2. For this situation the second step is "empty" one because in accordance with the restriction S it is forbidden to apply the IE to the points of the line segment [0, 5] at the second step.

The third step.

  1. For this situation we use the next standard weight 2 and subdivide the line segment [8, 13] by the IE in the Fibonacci ratio: 5 = 2 + 3. There are two situations (f) and (g) after the third step.
  2. We can return to the situation (b) at the third step. In accordance with the restriction of S we can apply the IE to the points of the line segment [0, 5] at the third step. We can use the standard weight 2 and subdivide the line segment [0, 5] by the IE in the Fibonacci ratio: 5 = 2 + 3. There are two situations (h) and (i) after the third step.

It is easily to trace the acting of the algorithm for the next two steps.

One can see from this example that the essence of the Fibonacci measurement algorithm is the subdivision of the "indeterminacy interval" obtained at the preceding step in the Fibonacci ratio. It is easily to see that this general principle is valid for any arbitrary p. The subdivision of the "indeterminacy interval" in this case is effected according to the recurrent correlation for the p-Fibonacci numbers.

And now we have the right to be surprised by the might and the logic of mathematical research. We begun to develop our algorithmic measurement theory without any connection with Fibonacci numbers. And we have come up to Fibonacci numbers again! Fibonacci had discovered his famous numbers at the solution of the "rabbits reproduction" problem. But we have discovered Fibonacci numbers in other Fibonacci's problem, the "weighing problem"!

Two fundamental problems advanced in the ancient time played an important role in the development of science. Those were the measurement problem and problem of Universe harmony. Later these problems combined by the main Pythagorean doctrine "Everything is a number" developed separately. The first problem connected with the discovery of the incommensurable line segments played an important role in the development of mathematics and brought into being the concept of irrational numbers; the second problem connected with the golden section had influenced on art and aesthetics.

The Italian mathematician Leonardo Pisano (Fibonacci) became famous for two mathematical discoveries, viz. the "weighing problem", which is the first optimization problem in the measurement theory, and the "rabbit reproduction problem", which gave Fibonacci numbers. The "Asymmetry Principle of Measurement" applied by the Ukrainian scientist A. Stakhov to the "weighing problem" joined both Fibonacci's problems and shoved that both problems are based on the common mathematical apparatus, namely Fibonacci numbers! And this fact is the first unexpected result following from the "algorithmic measurement theory"! But there exist other unexpected results following from the "algorithmic measurement theory". And we will tell about them at the next pages of our Museum. Follow us!