Tag Archives: Mathematics

Perception of complexity

In previous posts, the nature of reality and its complexity has been approached from the point of view of Information Theory. However, it is interesting to make this analysis from the point of view of human perception and thus obtain a more intuitive view.

Obviously, making an exhaustive analysis of reality from this perspective is complex due to the diversity of the organs of perception and the physiological and neurological aspects that develop over them. In this sense, we could explain how the information perceived is processed, depending on each of the organs of perception. Especially the auditory and visual systems, as these are more culturally relevant. Thus, in the post dedicated to color perception it has been described how the physical parameters of light are encoded by the photoreceptor cells of the retina.

However, in this post the approach will consist of analyzing in an abstract way how knowledge influences the interpretation of information, in such a way that previous experience can lead the analysis in a certain direction. This behavior establishes a priori assumptions or conditions that limit the analysis of information in all its extension and that, as a consequence, prevent to obtain certain answers or solutions. Overcoming these obstacles, despite the conditioning posed by previous experience, is what is known as lateral thinking.

To begin with, let’s consider the case of series math puzzles in which a sequence of numbers, characters, or graphics is presented, asking how the sequence continues. For example, given the sequence “IIIIIIIVVV”, we are asked to determine which the next character is. If the Roman culture had not developed, it could be said that the next character is “V”, or also that the sequence has been made by little scribblers. But this is not the case, so the brain begins to engineer determining that the characters can be Roman and that the sequence is that of the numbers “1,2,3,…”.  Consequently, the next character must be “I”.

In this way, it can be seen how the knowledge acquired conditions the interpretation of the information perceived by the senses. But from this example another conclusion can be drawn, consisting of the ordering of information as a sign of intelligence. To expose this idea in a formal way let’s consider a numerical sequence, for example the Fibonacci series “0,1,2,3,5,8,…”. Similarly to the previous case, the following number should be 13, so that the general term can be expressed as fn=fn-1+fn-2. However, we can define another discrete mathematical function that takes the values “0,1,2,3,5,8” for n = 0,1,2,3,4,5, but differs for the rest of the values of n belonging to the natural numbers, as shown in the following figure. In fact, with this criterion it is possible to define an infinite number of functions that meet this criterion.

The question, therefore, is: What is so special about the Fibonacci series in relation to the set of functions that meet the condition defined above?

Here we can make the argument already used in the case of the Roman number series. So that mathematical training leads to identifying the series of numbers as belonging to the Fibonacci series. But this poses a contradiction, since any of the functions that meet the same criterion could have been identified. To clear up this contradiction, Algorithmic Information Theory (AIT) should be used again.

Firstly, it should be stressed that culturally the game of riddles implicitly involves following logical rules and that, therefore, the answer is free from arbitrariness. Thus, in the case of number series the game consists of determining a rule that justifies the result. If we now try to identify a simple mathematical series that determines the sequence “0,1,2,3,5,8,…” we see that the expression fn=fn-1+fn-2 fulfills these requirements. In fact, it is possible that this is the simplest within this type of expressions. The rest are either complex, arbitrary or simple expressions that follow different rules from the implicit rules of the puzzle.

From the AIT point of view, the solution that contains the minimum information and can therefore be expressed most readily will be the most likely response that the brain will give in identifying a pattern determined by a stimulus. In the example above, the description of the predictable solution will be the one composed of:

  • A Turing machine.
  • The information to code the calculus rules.
  • The information to code the analytical expression of the simplest solution. In the example shown it corresponds to the expression of the Fibonacci series.

Obviously, there are solutions of similar or even less complexity, such as the one performed by a Turing machine that periodically generates the sequence “0,1,2,3,5,8”. But in most cases the solutions will have a more complex description, so that, according to the AIT, in most cases their most compact description will be the sequence itself, which cannot be compressed or expressed analytically.

For example, it is easy to check that the function:

generates for integer values of n the sequence “0,1,1,2,3,5,8,0,-62,-279,…”, so it could be said that the quantities following the proposed series are “…,0,-62,-279,… Obviously, the complexity of this sequence is higher than that of the Fibonacci series, as a result of the complexity of the description of the function and the operations to be performed.

Similarly, we can try to define other algorithms that generate the proposed sequence, which will grow in complexity. This shows the possibility of interpreting the information from different points of view that go beyond the obvious solutions, which are conditioned by previous experiences.

If, in addition to all the above, it is considered that, according to Landauer’s principle, information complexity is associated with greater energy consumption, the resolution of complex problems not only requires a greater computational effort, but also a greater energy effort.

This may explain the feeling of satisfaction produced when a certain problem is solved, and the tendency to engage in relaxing activities that are characterized by simplicity or monotony. Conversely, the lack of response to a problem produces frustration and restlessness.

This is in contrast to the idea that is generally held about intelligence. Thus, the ability to solve problems such as the ones described above is considered a sign of intelligence. But on the contrary, the search for more complex interpretations does not seem to have this status. Something similar occurs with the concept of entropy, which is generally interpreted as disorder or chaos and yet from the point of view of information it is a measure of the amount of information.

Another aspect that should be highlighted is the fact that the cognitive process is supported by the processing of information and, therefore, subject to the rules of mathematical logic, whose nature is irrefutable. This nuance is important, since emphasis is generally placed on the physical and biological mechanisms that support the cognitive processes, which may eventually be assigned a spiritual or esoteric nature.

Therefore, it can be concluded that the cognitive process is subject to the nature and structure of information processing and that from the formal point of view of the Theory of Computability it corresponds to a Turing machine. In such a way that nature has created a processing structure based on the physics of emerging reality – classical reality -, materialized in a neural network, which interprets the information coded by the perception senses, according to the algorithmic established by previous experience. As a consequence, the system performs two fundamental functions, as shown in the figure:

  • Interact with the environment, producing a response to the input stimuli.
  • Enhance the ability to interpret, acquiring new skills -algorithmic- as a result of the learning capacity provided by the neural network. 

But the truth is that the input stimuli are conditioned by the sensory organs, which constitute a first filter of information and therefore they condition the perception of reality. The question that can be raised is: What impact does this filtering have on the perception of reality?

On the complexity of PI (π)

Introduction

There is no doubt that since the origins of geometry humans have been seduced by the number π. Thus, one of its fundamental characteristics is that it determines the relationship between the length of a circumference and its radius. But this does not stop here, since this constant appears systematically in mathematical and scientific models that describe the behavior of nature. In fact, it is so popular that it is the only number that has its own commemorative day. The great fascination around π has raised speculations about the information encoded in its figures and above all has unleashed an endless race for its determination, having calculated several tens of billions of figures to date.

Formally, the classification of real numbers is done according to the rules of calculus. In this way, Cantor showed that real numbers can be classified as countable infinities and uncountable infinities, what are commonly called rational and irrational. Rational numbers are those that can be expressed as a quotient of two whole numbers. While irrational numbers cannot be expressed this way. These in turn are classified as algebraic numbers and transcendent numbers. The former correspond to the non-rational roots of the algebraic equations, that is, the roots of polynomials. On the contrary, transcendent numbers are solutions of transcendent equations, that is, non-polynomial, such as exponential and trigonometric functions.

Georg Cantor. Co-creator of Set Theory

Without going into greater detail, what should catch our attention is that this classification of numbers is based on positional rules, in which each figure has a hierarchical value. But what happens if the numbers are treated as ordered sequences of bits, in which the position is not a value attribute.  In this case, the Algorithmic Information Theory (AIT) allows to establish a measure of the information contained in a finite sequence of bits, and in general of any mathematical object, and that therefore is defined in the domain of natural numbers.

What does the AIT tell us?

This measure is based on the concept of Kolmogorov complexity (KC). So that, the Kolmogorov complexity K(x) of a finite object x is defined as the length of the shortest effective binary description of x. Where the term “effective description” connects the Kolmogorov complexity with the Theory of Computation, so that K(x) would correspond to the length of the shortest program that prints x and enters the halt state. To be precise, the formal definition of K(x) is:

K(x) = minp,i{K(i) + l(p):Ti (p) = x } + O(1)

Where Ti(p) is the Turing machine (TM) i that executes p and prints x, l(p) is the length of p, and K(i) is the complexity of Ti. Therefore, object p is a compressed representation of object x, relative to Ti, since x can be retrieved from p by the decoding process defined by Ti, so it is defined as meaningful information. The rest is considered as meaningless, redundant, accidental or noise (meaningless information). The term O(1) indicates that K(i) is a recursive function and in general it is non-computable, although by definition it is machine independent, and whose result has the same order of magnitude in each one of the implementations. In this sense, Gödel’s incompleteness theorems, Turing machine and Kolmogorov complexity lead to the same conclusion about undecidability, revealing the existence of non-computable functions.

KC shows that information can be compressed, but does not establish any general procedure for its implementation, which is only possible for certain sequences. In effect, from the definition of KC it is demonstrated that this is an intrinsic property of bitstreams, in such a way that there are sequences that cannot be compressed. Thus, the number of n-bit sequences that can be encoded by m bits is less than 2m, so the fraction of n-bit sequences with K(x) ≥ n-k is less than 2-k. If the n-bit possible sequences are considered, each one of them will have a probability of occurrence equal to 2-n, so the probability that the complexity of a sequence is K(x) ≥ n-k is equal to or greater than (1-2-k). In short, most bit sequences cannot be compressed beyond their own size, showing a high complexity as they do not present any type of pattern. Applied to the field of physics, this behavior justifies the ergodic hypothesis. As a consequence, this means that most of the problems cannot be solved analytically, since they can only be represented by themselves and as a consequence they cannot be described in a compact way by means of formal rules.

It could be thought that the complexity of a sequence can be reduced at will, by applying a coding criterion that modifies the sequence into a less complex sequence. In general, this only increases the complexity, since in the calculation of K(x) we would have to add the complexity of the coding algorithm that makes it grow as n2. Finally, add that the KC is applicable to any mathematical object, integers, sets, functions, and it is demonstrated that, as the complexity of the mathematical object grows, K(x) is equivalent to the entropy H defined in the context of Information Theory. The advantage of AIT is that it performs a semantic treatment of information, being an axiomatic process, so it does not require having a priori any type of alphabet to perform the measurement of information.

What can be said about the complexity of π?

According to its definition, KC cannot be applied to irrational numbers, since in this case the Turing machine does not reach the halt state, and as we know these numbers have an infinite number of digits. In other words, and to be formally correct, the Turing machine is only defined in the field of natural numbers (it must be noted that their cardinality is the same as that of the rationals), while irrational numbers have a cardinality greater than that of rational numbers. This means that KC and the equivalent entropy H of irrational numbers are undecidable and therefore non-computable.

To overcome this difficulty we can consider an irrational number X as the concatenation of a sequence of bits composed of a rational number x and a residue δx, so that in numerical terms X=x+δx, but in terms of information X={x,δx}. As a consequence, δx is an irrational number δx→0, and therefore δx is a sequence of bits with an undecidable KC and hence non-computable. In this way, it can be expressed:

K(X) = K(x)+K(δx)

The complexity of X can be assimilated to the complexity of x. A priori this approach may seem surprising and inadmissible, since the term K(δx) is neglected when in fact it has an undecidable complexity. But this is similar to the approximation made in the calculation of the entropy of a continuous variable or to the renormalization process used in physics, in order to circumvent the complexity of the underlying processes that remain hidden from observable reality.

Consequently, the sequence p, which runs the Turing machine i to get x, will be composed of the concatenation of:

  • The sequence of bits that encode the rules of calculus in the Turing machine i.
  • The bitstream that encodes the compressed expression of x, for example a given numerical series of x.
  • The length of the sequence x that is to be decoded and that determines when the Turing machine should reach the halt state, for example a googol (10100).

In short, it can be concluded that the complexity K(x) of known irrational numbers, e.g. √2, π, e,…, is limited. For this reason, the challenge must be to obtain the optimum expression of K(x) and not the figures that encode these numbers, since according to what has been said, their uncompressed expression, or the development of their figures, has a high degree of redundancy (meaningless information).

What in theory is a surprising and questionable fact is in practice an irrefutable fact, since the complexity of δx will always remain hidden, since it is undecidable and therefore non-computable.

Another important conclusion is that it provides a criterion for classifying irrational numbers into two groups: representable and non-representable. The former correspond to irrational numbers that can be represented by mathematical expressions, which would be the compressed expression of these numbers. While non-representable numbers would correspond to irrational numbers that could only be expressed by themselves and are therefore undecidable. In short, the cardinality of representable irrational numbers is that of natural numbers. It should be noted that the previous classification criterion is applicable to any mathematical object.

On the other hand, it is evident that mathematics, and calculus in particular, de facto accepts the criteria established to define the complexity K(x). This may go unnoticed because, traditionally in this context, numbers are analyzed from the perspective of positional coding, in such a way that the non-representable residue is filtered out through the concept of limit, in such a way that δx→0. However, when it comes to evaluating the informative complexity of a mathematical object, it may be required to apply a renormalization procedure.